这题是回溯里的经典题。它和全排列子集括号生成最大的不同是元素可以重复使用这是核心。一、这题本质是什么比如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 而不是 i1这是整题关键。因为元素可以重复使用例如2 - 2 - 2所以dfs(i)表示当前数字还能继续选如果写dfs(i 1)就变成一个数字只能用一次那就是另一题组合总和 II六、完整代码重点理解class Solution { ListListInteger res new ArrayList(); ListInteger path new ArrayList(); public ListListInteger 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 target7开始path[] target7选2path[2] target5再选2path[2,2] target3再选2path[2,2,2] target1再选2target-1结束。回溯path[2,2]然后尝试3path[2,2,3] target0加入答案。八、这题和子集有什么区别子集每个元素选 / 不选组合总和每个元素可以选无限次所以dfs(i)而不是dfs(i1)九、回溯题统一模板你会发现路径 path 结果 res for循环枚举选择 递归 撤销选择几乎所有回溯题都这样。只是变化题目不同点全排列用used数组子集每层直接加入答案组合总和dfs(i)可重复使用括号生成有左右括号限制本质都是在决策树上DFS