39. 组合总和

这题是回溯里的经典题。

它和：

• 全排列

• 子集

• 括号生成

最大的不同是：

元素可以重复使用

这是核心。

一、这题本质是什么？

比如：

candidates = [2,3,5] target = 8

你需要：

不断尝试选数字 直到总和 == 8

例如：

2 -> 2 -> 2 -> 2

或者：

2 -> 3 -> 3

二、回溯模板怎么想？

回溯其实就一句话：

尝试 -> 递归 -> 撤销选择

三、决策树（真正理解）

以：

[2,3,6,7] target = 7

为例。

从空开始：

[]

第一层：

选2 选3 选6 选7

如果先选2：

[2] 剩余 target = 5

继续：

[2,2] 剩余3

继续：

[2,2,2] 剩余1

已经不可能：

因为最小是2。

回溯。

然后：

[2,2,3] 剩余0

找到答案。

四、为什么不会出现重复组合？

比如：

[2,2,3] 和 [2,3,2]

其实是同一种。

怎么避免？

用 start 参数

意思是：

后面只能从当前及以后开始选

例如：

当你已经选了2：

下一层还能选：

2 3 6 7

但如果已经选了3：

下一层只能选：

3 6 7

不能再回头选2。

这样天然去重。

五、为什么这里递归传 i 而不是 i+1？

这是整题关键。

因为元素可以重复使用

例如：

2 -> 2 -> 2

所以：

dfs(i)

表示：

当前数字还能继续选

如果写：

dfs(i + 1)

就变成：

一个数字只能用一次

那就是另一题：

组合总和 II

六、完整代码（重点理解）

class Solution { List<List<Integer>> res = new ArrayList<>(); List<Integer> path = new ArrayList<>(); public List<List<Integer>> combinationSum(int[] candidates, int target) { dfs(candidates, target, 0); return res; } private void dfs(int[] candidates, int target, int start) { // 找到答案 if (target == 0) { res.add(new ArrayList<>(path)); return; } // 剪枝 if (target < 0) { return; } for (int i = start; i < candidates.length; i++) { // 选择 path.add(candidates[i]); // 递归 dfs(candidates, target - candidates[i], i); // 回溯 path.remove(path.size() - 1); } } }

七、执行流程（必须看懂）

例如：

2 3 6 7 target=7

开始：

path=[] target=7

选2：

path=[2] target=5

再选2：

path=[2,2] target=3

再选2：

path=[2,2,2] target=1

再选2：

target=-1

结束。

回溯：

path=[2,2]

然后尝试3：

path=[2,2,3] target=0

加入答案。

八、这题和子集有什么区别？

子集

每个元素：

选 / 不选

组合总和

每个元素：

可以选无限次

所以：

dfs(i)

而不是：

dfs(i+1)

九、回溯题统一模板

你会发现：

路径 path 结果 res for循环枚举选择 递归 撤销选择

几乎所有回溯题都这样。

只是变化：

本质都是：

在决策树上DFS