组合总和如何用回溯法求解？（LeetCode 39）

简化版

给一组互不相同的正整数 candidates 和目标 target，每个数可以重复使用无数次，求所有和为 target 的组合。用回溯：从 start 往后选数，选中就把 target 减去它、递归；因为能重复用，递归时下标还传 i（不是 i+1）。用 start 保证组合不重复；先排序后加剪枝「当前数已经大于剩余目标就 break」。

详细版

List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(candidates);                   // 排序，便于剪枝
    backtrack(candidates, target, 0, new ArrayList<>(), res);
    return res;
}
void backtrack(int[] c, int remain, int start, List<Integer> path, List<List<Integer>> res) {
    if (remain == 0) {                         // 剩余目标正好为 0，是一个解
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i < c.length; i++) {
        if (c[i] > remain) break;              // 排序后剪枝：它和后面的都超了
        path.add(c[i]);
        backtrack(c, remain - c[i], i, path, res); // 传 i：允许重复使用 c[i]
        path.remove(path.size() - 1);          // 撤销
    }
}

可重复用：递归传 i 而不是 i+1，所以下一层还能再选中 c[i]。
用 start 防重复组合：[2,2,3] 和 [2,3,2] 视为同一个，只按下标不减的顺序生成一次。
剪枝：排序后，若 c[i] > remain，因为后面的更大，直接 break 整个循环。
结束条件用「剩余目标 remain 减到 0」，比每次求和更省。

完整版教学

一、问题：可重复选、求和为 target 的组合

组合总和：candidates = [2,3,6,7]，target = 7，答案是 [[2,2,3],[7]]。特点有两个：

每个数可以用任意多次（2 用了两次）；
结果是组合（不看顺序），[2,2,3] 和 [2,3,2] 算同一个，只保留一个。

这两个特点分别决定了代码里「递归传 i」和「使用 start」两个关键写法。

二、允许重复用同一个数：递归传 i 而非 i+1

普通组合/子集里，选了下标 i 后递归传 i+1，表示「这个元素用过了，往后选」。但组合总和允许一个数用多次，所以选了 c[i] 之后，下一层还应该能再次选到 c[i]——于是递归时 start 仍传 i（而不是 i+1）。

backtrack(c, remain - c[i], i, ...)  // 注意是 i，下一层还能选 c[i]

这样 [2,2,2,...] 这类重复使用同一个数的组合才能被生成。若传 i+1，就退化成「每个数最多用一次」了。

三、用 start 避免重复组合

因为结果是组合、不看顺序，必须防止 [2,3] 和 [3,2] 都出现。手段还是 start 下标：每层只从 start 及之后选，元素按下标非递减顺序加入路径。这样任何一个组合都只会以「下标不回头」的唯一方式生成一次。

注意和上一节的配合：传 i（不是 i+1）允许重复用同一个 c[i]，但 start 从 i 起仍然不会往回退到 i 之前，所以不会产生顺序不同的重复。两者不矛盾——「能原地重复、但不能回头」。

四、排序 + 剪枝：c[i] > remain 就 break

开头 Arrays.sort(candidates) 是为了剪枝。排序后，for 循环里一旦发现 c[i] > remain（当前候选已经比剩余目标还大），因为后面的候选都更大、更不可能，就可以直接 break 掉整个循环，而不是 continue。

若没排序，只能对每个 i 单独判断（用 continue），错过「后面全部剪掉」的机会；
排序后用 break，把「当前及之后的所有更大候选」一次性剪掉，效率明显更高。

用「剩余目标 remain」递减、判 remain==0，也比每次重新累加路径求和更高效；remain < 0 的情况已被 c[i] > remain 的剪枝提前挡住，不会进入递归。

五、和组合总和 II 的区别

组合总和 II（LeetCode 40） 是常一起考的变体，两点不同：

每个数只能用一次 → 递归传 i+1（不能再选自己）；
candidates 含重复元素，但每个组合里同一个位置的重复值不能重复选 → 先排序，再加同层去重 if (i > start && c[i]==c[i-1]) continue;。

对比记忆：

	组合总和 I	组合总和 II
每个数能用几次	无限次（传 `i`）	一次（传 `i+1`）
元素是否有重复	无重复	有重复，需同层去重

六、把状态、选择与撤销画成决策树

本题递归状态的精确定义是：path 中候选下标非递减，remain 表示尚需凑出的和；允许复用时递归仍传 i。状态含义越清楚，结束条件、候选范围和去重位置越容易从题意推出。

进入节点：检查当前状态与剩余目标
枚举候选：先判断约束和剪枝条件
做选择：同步修改 path / used / 约束集合
递归下一层
撤销选择：恢复到进入本节点前的状态

带数字推演：候选 [2,3,6,7]、target=7：分支 2→2→3 和 7 命中，2→6 因超出被剪。画树时只需展开能体现“同层选择”和“纵向递归”区别的两三层，并标出被剪掉的分支，便能解释去重或剪枝为什么不会漏解。

记忆钩子：回溯不是“递归试一试”，而是维护状态不变量；做选择与撤销必须镜像，剪枝必须证明被删分支不可能产生答案。

七、复杂度、剪枝代价与实现边界

关键实现边界是：经典题要求候选为正数，否则 remain 不会单调下降，可能无限递归；候选重复版本需额外去重。回溯复杂度不能只写一个固定模板，应说明树深、每层分支数、合法叶子数以及复制答案的成本。

维度	自检问题
状态	参数能否唯一描述当前节点
候选	是否遗漏合法选择或重复枚举
剪枝	条件是必要条件还是拍脑袋
撤销	path、标记和计数是否全部恢复
输出	保存的是快照还是共享可变引用

测试应包含无解、唯一解、多解、最小规模、全部候选相同或冲突密集的输入。对可变字符串、棋盘和标记数组，还应在递归返回后断言状态与进入前一致；这类断言比只比较最终答案更容易定位撤销错误。

八、常见误区与追问

误区：允许重复选就不需要 start。 start 仍用于避免 [2,3] 与 [3,2] 的排列重复。
误区：递归下一层一定传 i+1。 可重复选当前数时应传 i。
误区：未排序也能遇到过大值就 break。 只有排序后后续值都更大，break 才安全。
追问：为什么正数是重要前提？ 每次选择让 remain 下降，保证终止并支持剪枝。
追问：组合总和 II 有何不同？ 每个元素最多使用一次，递归传 i+1，并做同层去重。
追问：复杂度如何说？ 依赖 target/最小候选形成的树深和分支数，通常指数级加输出成本。

九、加强记忆

组合总和 I 回溯：用 start 防重复组合，因可重复使用同一个数，递归传 i（不是 i+1）；结束条件是剩余目标 remain 减到 0。先排序以便剪枝——c[i] > remain 直接 break（后面更大全砍）。变体组合总和 II：每数只用一次（传 i+1）+ 数组有重复需「排序 + if (i>start && c[i]==c[i-1]) continue」同层去重。

简化版

详细版