给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
示例 1:
1
2
3
4
5
6
7
8
| 输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
|
示例 2:
1
2
3
4
5
6
| 输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
|
此题与第 39 题差不多，只是条件限制有些不同。我们首先写出允许重复的初始程序，然后再添加限制条件：
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
| class Solution {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
dfs(0, target, candidates, new ArrayDeque<Integer>());
return ans;
}
private void dfs(int start, int target, int[] candidates, ArrayDeque<Integer> path){
if(target == 0){
ans.add(new ArrayList(path));
return;
}
for(int index = start; index < candidates.length; index++){
int cur = candidates[index];
if(target - cur < 0){
break;
}
path.addLast(cur);
dfs(index + 1, target - cur, candidates, path);
path.removeLast();
}
}
}
|
当candidates = [1, 2, 2, 2, 5]，target = 5 时运行得到的结果为[[1,2,2],[1,2,2],[1,2,2],[5]]，[1, 2, 2]这个结果重复了三次。
想到可以在递归的时候限制，遇到重复的元素就跳过，我们写出如下版本（错误示例）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| private void dfs(int start, int target, int[] candidates, ArrayDeque<Integer> path){
if(target == 0){
ans.add(new ArrayList(path));
return;
}
for(int index = start; index < candidates.length; index++){
int cur = candidates[index];
if(target - cur < 0){
break;
}
if(index > 0 && candidates[index] == candidates[index - 1]){
continue;
}
path.addLast(cur);
dfs(index + 1, target - cur, candidates, path);
path.removeLast();
}
}
|
再次运行上述示例，我们得到结果[[5]]，[1, 2, 2]被剪掉了。当 index = 2 时，发现 index - 1 的值与它的值相同，则剪掉了这一分支，但我们需要保留这条分支。
1
2
3
4
5
| 1 index = 0 第 1 层
/
2 index = 1 第 2 层
/
2 index = 2 第 3 层
|
对于下图中的递归路径，我们需要保留左边的分支，删除右边的分支，使每层都可以保留一个与上一层相同的元素，同时在每一层中，只能有一个相同的元素。这样就保留了最左侧的分支。
具体的代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| private void dfs(int start, int target, int[] candidates, ArrayDeque<Integer> path){
if(target == 0){
ans.add(new ArrayList(path));
return;
}
for(int index = start; index < candidates.length; index++){
int cur = candidates[index];
if(target - cur < 0){
break;
}
if(index > start && candidates[index] == candidates[index - 1]){
continue;
}
path.addLast(cur);
dfs(index + 1, target - cur, candidates, path);
path.removeLast();
}
}
|
参考：weiwei哥的题解。