39 组合总数
题目描述
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates中的数字可以无限制重复被选取。
说明：
- 所有数字（包括
target）都是正整数。
- 解集不能包含重复的组合。
示例1:
1
2
3
4
5
6
| 输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
|
示例2:
1
2
3
4
5
6
7
| 输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]
|
思路
分治，把target 分解成 target - num[i]的问题，进行dfs 深度优先搜索即可。可以先进行排序，方便后续的处理。可以把每次选中的元素记录下来，进行累加得到sum，最终与target进行比较。如果 sum >= target ，则停止。
错误解法
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
| public class CombinationSum {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if (candidates == null || candidates.length == 0) {
return result;
}
Arrays.sort(candidates);
if (candidates[0] > target) {
return result;
}
dfs(0, target, candidates, new ArrayList<>());
return result;
}
public void dfs(int sum, int target, int[] candidates, List<Integer> currentList) {
if (sum > target) {
return;
}
if (sum == target) {
result.add(new ArrayList<>(currentList));
return;
}
for (int i = 0; i < candidates.length; i++) {
int temp = candidates[i];
currentList.add(temp);
dfs(sum + temp, target, candidates, currentList);
currentList.remove(currentList.size() - 1);
}
}
}
|
采用上述代码执行后，发现存在重复集的情况
原因如果选中2，则可形成[2,2,3]的组合，如果第一次选中3，则可形成[3,2,2]。很容易看到，进行向下dfs的时候，2的分支所有能到达target的组合都在选中2已经选中。所以在选3的分支，剔除2，继续从3的分支开始选即可。因此，我们dfs层面加入一个begin，表示从begin开始选即可。
正确解法
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
| public class CombinationSum {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if (candidates == null || candidates.length == 0) {
return result;
}
Arrays.sort(candidates);
if (candidates[0] > target) {
return result;
}
dfs(0, target, candidates, new ArrayList<>(), 0);
return result;
}
public void dfs(int sum, int target, int[] candidates, List<Integer> currentList, int begin) {
if (sum == target) {
result.add(new ArrayList<>(currentList));
return;
}
for (int i = begin; i < candidates.length; i++) {
int temp = candidates[i];
if (temp + sum > target) {
break;
}
currentList.add(temp);
dfs(sum + temp, target, candidates, currentList, i);
currentList.remove(currentList.size() - 1);
}
}
|
结果
