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
31
32
33
34
35
36
37
38
39
40
41
| List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
int[] tmp = new int[candidates.length];
Arrays.sort(candidates);
dfs(candidates, target, 0, 0, tmp, 0);
return list;
}
private void dfs(int[] candidates, int target, int k, int sum, int[] tmp, int dpth) {
if(sum==target) {
List<Integer> list2 = new ArrayList<>();
for(int i=0; i<dpth;i++) {
list2.add(tmp[i]);
}
list.add(list2);
return ;
}
if(sum>target) {
return ;
}
for(int i = k; i<candidates.length; i++) {
tmp[dpth] = candidates[i];
dfs(candidates, target, i+1, sum+candidates[i], tmp, dpth+1);
while(i+1<candidates.length&&candidates[i]==candidates[i+1])i++;
}
}
|
