1. Description

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

2. Runtime Distribution

3. Submission Details

4. Example

given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

5. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active"]

public List> combinationSum(int[] candidates, int target) {
	List> results = new ArrayList>();
	if (candidates == null || candidates.length == 0 || target <= 0) {
		return results;
	}
	Arrays.sort(candidates);
	LinkedList records = new LinkedList();
	dfs(candidates, -1, records, results, target);
	return results;
}

private void dfs(int[] candidates, int start, LinkedList records, List> results,
		int target) {
	if (target == 0) {
		results.add(new LinkedList(records));
	}
	if (target <= 0) {
		return;
	}
	int pre = -1;
	for (int i = start + 1; i < candidates.length; i++) {
		if (candidates[i] == pre) {
			continue;
		}
		records.offer(candidates[i]);
		dfs(candidates, i, records, results, target - candidates[i]);
		records.pollLast();
		pre = candidates[i];
	}
}

[/restab]
[/restabs]

6.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active" ]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class LeetCode0039 {
	public List> combinationSum(int[] candidates, int target) {
		List> results = new ArrayList>();
		if (candidates == null || candidates.length == 0 || target <= 0) {
			return results;
		}
		Arrays.sort(candidates);
		LinkedList records = new LinkedList();
		dfs(candidates, -1, records, results, target);
		return results;
	}

	private void dfs(int[] candidates, int start, LinkedList records, List> results,
			int target) {
		if (target == 0) {
			results.add(new LinkedList(records));
		}
		if (target <= 0) {
			return;
		}
		int pre = -1;
		for (int i = start + 1; i < candidates.length; i++) {
			if (candidates[i] == pre) {
				continue;
			}
			records.offer(candidates[i]);
			dfs(candidates, i, records, results, target - candidates[i]);
			records.pollLast();
			pre = candidates[i];
		}
	}

	public static void main(String[] args) {
		LeetCode0039 leetcode = new LeetCode0039();
		int[] candidates = { 10, 1, 2, 7, 6, 1, 5 };
		List> results = leetcode.combinationSum(candidates, 8);
		for (int i = 0; i < results.size(); i++) {
			for (int j = 0; j < results.get(i).size(); j++) {
				System.out.print(results.get(i).get(j) + " ");
			}
			System.out.println();
		}
	}
}

[/restab]
[/restabs]