05 August 2008
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates`may only be used once in the combination.
Note:
Example 1:
1
2
3
4
5
6
7
8
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:
1
2
3
4
5
6
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]
有重复元素，必须排序和跳过重复元素。这道题需要找unique的组合，例如[2,2,3], target = 5，这时候只返回一个[2, 3]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> results = new ArrayList<>();
if (candidates == null || candidates.length == 0) {
return results;
}
Arrays.sort(candidates);
dfs(candidates, results, new ArrayList<>(), target, 0, 0);
return results;
}
private void dfs(int[] candidates, List<List<Integer>> result, List<Integer> oneResult, int target, int sum, int index) {
if (sum == target) {
result.add(new ArrayList<>(oneResult));
return;
}
if (sum > target) {
return;
}
for (int i = index; i < candidates.length; i++) {
if (i > index && (candidates[i] == candidates[i - 1])) { //选过了，防止重复combinations
continue;
}
oneResult.add(candidates[i]);
//跟i比，这里换成i + 1，不使用刚才的重复数字
dfs(candidates, result, oneResult, target, sum + candidates[i], i + 1);
oneResult.remove(oneResult.size() - 1);
}
}
}