排序 + 选或不选, 这里比较subtle的是重复问题, 假如x = can[i], x’ = can[i+1], 选x不选x’ 不选x’选x 这样就会导致重复, 为了避免重复, 我们如果不选, 就要跳过所有和当前can相等的can
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
| class Solution {
int[] candidates;
List<Integer> path;
List<List<Integer>> ans;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
this.ans = new ArrayList<>();
path = new ArrayList<>();
this.candidates = candidates;
Arrays.sort(candidates);
dfs(0, target);
return ans;
}
private void dfs(int i, int target) {
if (target == 0) {
ans.add(new ArrayList<>(path));
return ;
}
if (target < 0) return ;
if (i >= candidates.length) return ;
int x = candidates[i];
path.add(x);
dfs(i+1, target - x);
path.remove(path.size()-1);
i++;
while (i < candidates.length && candidates[i] == candidates[i-1]) {
i++;
}
dfs(i, target);
}
}
|
