一、题目描述
给定一个无重复元素的正整数数组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 List<List<Integer>> res = new LinkedList<>(); // 保存当前搜索路径 private final LinkedList<Integer> route = new LinkedList<>(); // 当前路径中所有数字之和 private int sum = 0; public List<List<Integer>> 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，又能允许同一个数字被重复使用。当总和超过目标值时，再利用正整数条件提前剪枝。
