一、题目描述给定一个无重复元素的正整数数组candidates和一个目标整数target找出所有数字之和等于target的不同组合。数组中的同一个数字可以被重复选择。如果至少有一个数字的选择次数不同就认为是不同组合。题目允许以任意顺序返回答案。例如输入candidates [2, 3, 6, 7], target 7 输出[[2, 2, 3], [7]]数字2可以重复使用因此可以得到组合[2,2,3]数字7本身也等于目标值所以[7]也是一个有效组合。这道题的难点主要有两个同一个数字可以无限次使用[2,2,3]和[3,2,2]只能算作一种组合。解决这两个问题的关键就是DFS、回溯和start起始下标。二、把组合过程看成一棵决策树假设candidates [3, 4, 5], target 9从空组合开始第一轮可以选择3、4或5。选择一个数字后再继续选择下一个数字直到当前总和等于或者超过target。例如先选择3当前路径为[3]总和为3。因为数字可以重复使用下一层仍然可以选择3得到[3,3]继续选择3后得到[3,3,3]总和正好为9因此找到一个有效组合。如果先选择4再选择5可以得到[4,5]。但如果第一轮选择5第二轮再选择4就会得到[5,4]。两者包含的数字和数量完全相同本质上是同一种组合不能重复加入答案。因此我们不能让每一层都从数组下标0开始遍历而要通过一个start参数控制下一层的选择范围。三、start如何避免重复组合start表示当前这一层可以从candidates的哪个位置开始选择。for (int i start; i candidates.length; i) { // 选择 candidates[i] }假设当前第一次选择的是下标1对应的数字4那么后续只能继续选择下标大于或等于1的数字即4和5不能再回头选择下标0的数字3。这样一来可以生成[4,5]但不会再生成顺序相反的[5,4]。所有组合都会按照候选数组中的下标顺序构造从而自然避免重复。这里要区分两个容易混淆的概念start限制的是当前层可以选择的起点用来避免不同排列产生重复组合递归时传入i而不是i 1用来允许当前数字被重复使用。核心递归调用如下traverseTree(candidates, target, i);如果传入i 1当前数字在下一层就不能再次被选择这将变成“每个数字最多使用一次”的另一类组合问题。可以把这条规律记成一句话start负责去重传入i负责复用。四、递归终止条件与剪枝搜索过程中需要根据当前路径总和sum判断是否继续递归。1. 找到有效组合当sum target时说明当前路径是一组有效答案if (sum target) { res.add(new ArrayList(route)); return; }这里必须创建一个新的ArrayList保存当前路径的快照。不能直接将route放入结果集因为route在后续回溯过程中还会继续修改。2. 当前总和超过目标值当sum target时可以直接结束当前分支if (sum target) { return; }题目保证候选数字都是正整数。总和一旦超过target继续添加数字只会使总和更大当前分支不可能再得到有效答案因此可以提前剪枝。例如目标值为9当前路径为[5,5]总和已经是10就没有继续搜索的必要。五、回溯的完整过程在每一层递归中需要完成“选择、递归、撤销选择”三个动作route.add(candidates[i]); sum candidates[i]; traverseTree(candidates, target, i); route.removeLast(); sum - candidates[i];先把当前数字加入路径并更新总和然后进入下一层继续搜索。递归返回后删除刚刚加入的数字同时恢复sum让程序回到选择该数字之前的状态再尝试同一层的其他候选数字。例如搜索[3,3,3]并记录答案后需要依次回退到[3,3]、[3]。只有恢复原来的路径和总和才能继续尝试[3,3,4]、[3,4]等其他分支。如果只删除路径末尾元素却没有恢复sum路径和总和就会不一致后面的判断也会全部出错。六、完整 Java 代码下面的实现与上述思路一致import java.util.ArrayList; import java.util.LinkedList; import java.util.List; class Solution { // 保存所有符合条件的组合 private final ListListInteger res new LinkedList(); // 保存当前搜索路径 private final LinkedListInteger route new LinkedList(); // 当前路径中所有数字之和 private int sum 0; public ListListInteger combinationSum(int[] candidates, int target) { traverseTree(candidates, target, 0); return res; } private void traverseTree(int[] candidates, int target, int start) { // 当前路径正好满足要求 if (sum target) { res.add(new ArrayList(route)); return; } // 数组元素均为正数超过目标值后无法再恢复 if (sum target) { return; } // 只从 start 开始选择避免产生重复排列 for (int i start; i candidates.length; i) { // 做出选择 route.add(candidates[i]); sum candidates[i]; // 仍从 i 开始允许 candidates[i] 被重复选择 traverseTree(candidates, target, i); // 撤销选择恢复进入递归前的状态 route.removeLast(); sum - candidates[i]; } } }七、示例执行过程以candidates [2,3,6,7]、target 7为例。搜索首先从2开始[] → [2] → [2,2] → [2,2,2]在[2,2]的基础上选择3得到[2,2,3]总和等于7记录答案。回溯后继续尝试其他数字超过7的分支会直接返回。当第一层选择3时后续只能继续选择3、6、7不能再回头选择2因此不会生成[3,2,2]。最后第一层选择7得到第二个有效组合[7]。最终结果为[[2, 2, 3], [7]]八、复杂度分析回溯算法需要枚举可能的组合时间复杂度与候选数字及目标值有关。若最小候选数字为m决策树最大深度约为target / m最坏情况下搜索规模呈指数级增长可粗略理解为O(n^(target/m))。空间复杂度主要来自递归调用栈和当前路径最大递归深度约为target / m因此额外空间复杂度为O(target/m)不计算最终答案占用的空间。九、常见错误1. 每层都从零开始遍历这样会同时产生[2,2,3]和[3,2,2]造成组合重复。应当使用start控制选择范围。2. 递归时传入i 1这会导致同一个数字无法重复使用漏掉[2,2,3]这样的答案。本题应当继续传入i。3. 直接把route加入结果集route是一个不断变化的对象必须使用new ArrayList(route)保存路径快照。4. 递归后忘记恢复状态回溯时既要删除末尾数字也要减去该数字使route和sum同时恢复。5. 忽略剪枝成立的前提sum target后能够直接返回是因为题目中的候选数字都是正整数。如果允许负数就不能使用这一剪枝逻辑。十、总结组合总和是一道典型的回溯题。我们通过 DFS 枚举所有可能的选择使用route维护当前组合使用sum判断当前状态并在递归返回后撤销选择。本题最关键的是start参数同一层只从start之后选择可以避免不同顺序产生重复组合递归时继续传入当前下标i又能允许同一个数字被重复使用。当总和超过目标值时再利用正整数条件提前剪枝。