39. 组合总和——combination-sum
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
1
2
3
4
5
6
| 输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
|
示例 2：
1
2
| 输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
|
示例 3：
1
2
| 输入: candidates = [2], target = 1
输出: []
|
提示：
1 <= candidates.length <= 302 <= candidates[i] <= 40candidates 的所有元素 互不相同1 <= target <= 40
- 我的第一想法就是递归，每次从头开始加，递归结束条件是跟结果相等或大于结果，等于结果就加入结果列表
我的错误答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<Integer> list = new ArrayList<>();
getResult(candidates, 0, 0, target, list);
return ans;
}
private void getResult(int[] candidates, int index, int currSum, int target, List<Integer> list) {
if (currSum == target) {
ans.add(list);
}
if (currSum < target) {
for (int i = index; i < candidates.length; i++) {
list.add(candidates[i]);
getResult(candidates, index, currSum + candidates[index], target, list);
}
}
if (currSum > target) {
return;
}
}
}
|
问题：
1. 回溯缺失：递归后没有 “撤销选择”
组合问题的核心是 “选→递归→不选”（回溯），你只做了 “选”，没做 “撤销”，会导致列表里的元素越积越多，最终结果全是重复且错误的。
2. 结果添加错误：直接 add (list) 会导致后续修改影响已保存的结果
ans.add(list) 加的是列表的引用，后续递归中修改 list（add/remove）会同步改变 ans 里的元素，应该加new ArrayList<>(list)（复制新列表）。
3. 递归终止条件顺序错误
先判断currSum == target，但没立刻 return，会继续执行后面的currSum < target逻辑，导致多加元素。
思路
1. 回溯的 “选→递归→撤销” 逻辑
组合问题的本质是 “枚举所有可能的选择”，但要避免无效枚举和重复组合：
- 选：把当前元素加入临时列表
path，更新当前和；
- 递归：继续选择（因为元素可重复选，所以递归的起始下标传
i，不是i+1—— 这样下次还能选当前元素）；
- 撤销：递归返回后，把最后加入的元素从
path删掉，回到上一步，尝试下一个元素。
2. 为什么从index开始遍历？
比如候选数组[2,3,6,7]，目标 7：
- 如果从 0 开始遍历，会枚举
[2,2,3]；
- 如果允许从 0 之前的下标遍历，会出现
[2,3,2]（和[2,2,3]重复）；
- 从
index开始遍历，保证组合是 “非降序” 的，天然避免重复组合。
3. 示例 1 的执行流程（帮你理解）
plaintext
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| 候选：[2,3,6,7]，目标7
1. 选2 → 当前和=2 → 递归（index=0）
选2 → 当前和=4 → 递归（index=0）
选2 → 当前和=6 → 递归（index=0）
选2 → 当前和=8 >7 → 返回，撤销2（和=6）
选3 → 当前和=9 >7 → 返回，撤销3（和=6）
选6 → 当前和=12 >7 → 返回，撤销6（和=6）
选7 → 当前和=13 >7 → 返回，撤销7（和=6）
撤销2（和=4）→ 选3 → 当前和=7 → 保存[2,2,3]，返回
选6 → 当前和=10 >7 → 返回，撤销6（和=4）
选7 → 当前和=11 >7 → 返回，撤销7（和=4）
撤销2（和=2）→ 选3 → 当前和=5 → 递归（index=1）
选3 → 当前和=8 >7 → 返回，撤销3（和=5）
选6 → 当前和=11 >7 → 返回，撤销6（和=5）
选7 → 当前和=12 >7 → 返回，撤销7（和=5）
选6 → 当前和=8 >7 → 返回，撤销6（和=2）
选7 → 当前和=9 >7 → 返回，撤销7（和=2）
2. 撤销2（和=0）→ 选3 → 当前和=3 → 递归（index=1）
...（略，最终和不够或超过）
3. 选6 → 当前和=6 → 递归（index=2）
选6 → 当前和=12 >7 → 返回
选7 → 当前和=13 >7 → 返回
4. 选7 → 当前和=7 → 保存[7]，返回
最终结果：[[2,2,3],[7]]
|
四、关键易错点总结
- 递归起始下标传
i（不是i+1）：允许重复选当前元素；
- 回溯必须
remove最后一个元素：否则列表会累积所有选择；
- 保存结果时要复制新列表：
new ArrayList<>(path)，避免引用传递的坑；（引用类型的传递规则—— 直接 add(list) 存的是 “列表的地址”，而非 “列表里的元素”，最终会导致结果集里的内容被回溯的 “撤销操作” 篡改；而 add(new ArrayList<>(path)) 是存 “当前元素的拷贝”，避免后续path.remove(path.size()-1); 的时候把结果也改了）
- 终止条件要先判断
currSum > target，再判断==，且判断==后要return。
我的思路的正确答案
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
42
| class Solution {
List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<Integer> path = new ArrayList<>();
backtrack(candidates, 0, 0, target, path);
return ans;
}
private void backtrack(int[] candidates, int index, int currSum, int target, List<Integer> path) {
if (currSum > target) {
return;
}
if (currSum == target) {
ans.add(new ArrayList<>(path));
return;
}
for (int i = index; i < candidates.length; i++) {
path.add(candidates[i]);
backtrack(candidates, i, currSum + candidates[i], target, path);
path.remove(path.size() - 1);
}
}
}
|
官方解答
跟我的想法一样：我之前就是把回溯写掉了
方法：搜索回溯
思路与算法
对于这类寻找所有可行解的题，我们都可以尝试用「搜索回溯」的方法来解决。
回到本题，我们定义递归函数 dfs(target,combine,idx) 表示当前在 candidates 数组的第 idx 位，还剩 target 要组合，已经组合的列表为 combine。递归的终止条件为 target≤0 或者 candidates 数组被全部用完。那么在当前的函数中，每次我们可以选择跳过不用第 idx 个数，即执行 dfs(target,combine,idx+1)。也可以选择使用第 idx 个数，即执行 dfs(target−candidates[idx],combine,idx)，注意到每个数字可以被无限制重复选取，因此搜索的下标仍为 idx。
更形象化地说，如果我们将整个搜索过程用一个树来表达，即如下图呈现，每次的搜索都会延伸出两个分叉，直到递归的终止条件，这样我们就能不重复且不遗漏地找到所有可行解：
当然，搜索回溯的过程一定存在一些优秀的剪枝方法来使得程序运行得更快，而这里只给出了最朴素不含剪枝的写法，因此欢迎各位读者在评论区分享自己的见解。
代码
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
| class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> combine = new ArrayList<Integer>();
dfs(candidates, target, ans, combine, 0);
return ans;
}
public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
if (idx == candidates.length) {
return;
}
if (target == 0) {
ans.add(new ArrayList<Integer>(combine));
return;
}
dfs(candidates, target, ans, combine, idx + 1);
if (target - candidates[idx] >= 0) {
combine.add(candidates[idx]);
dfs(candidates, target - candidates[idx], ans, combine, idx);
combine.remove(combine.size() - 1);
}
}
}
|
复杂度分析
- 时间复杂度：O(S)，其中 S 为所有可行解的长度之和。从分析给出的搜索树我们可以看出时间复杂度取决于搜索树所有叶子节点的深度之和，即所有可行解的长度之和。在这题中，我们很难给出一个比较紧的上界，我们知道 O(n×2n) 是一个比较松的上界，即在这份代码中，n 个位置每次考虑选或者不选，如果符合条件，就加入答案的时间代价。但是实际运行的时候，因为不可能所有的解都满足条件，递归的时候我们还会用 target−candidates[idx]≥0 进行剪枝，所以实际运行情况是远远小于这个上界的。
- 空间复杂度：O(target)。除答案数组外，空间复杂度取决于递归的栈深度，在最差情况下需要递归 O(target) 层。
