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.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
1
2
3
4
5
6
| [
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
if(candidates.length == 0) return ans;
Arrays.sort(candidates);
backtrace(ans, new ArrayList<Integer>() , candidates, target, 0);
return ans;
}
public void backtrace(List<List<Integer>> ans, ArrayList<Integer> t, int[] candidates, int target, int start){
if(target == 0){
ans.add(new ArrayList<Integer>(t));
}
for(int i=start; i<candidates.length; i++){
if(i!= start && candidates[i-1] == candidates[i])
continue;
if(candidates[i] > target)
return ;
t.add(candidates[i]);
backtrace(ans, t, candidates, target - candidates[i], i+1);
t.remove(t.size()-1);
}
}
}
|
- 注意有重复的情况
- [10,1,2,7,6,1,5]
8
- 如果没有continue操作，则会产生两个[1,7]
