浅挖一下Combination Sum (LC 39+40)

LeetCode 39. 组合总和（Combination Sum）

给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。 candidates 中的同一个数字可以无限制重复被选取，如果至少一个数字的被选数量不同，则两种组合是不同的。

例：candidates = [2,3,6,7], target = 7 → [[2,2,3],[7]]

LeetCode 40. 组合总和 II（Combination Sum II）

给你一个可能包含重复元素的整数数组 candidates和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合 candidates 中的每个数字在每个组合中只能使用一次。解集不能包含重复的组合。

例：candidates = [10,1,2,7,6,1,5], target = 8 → [[1,1,6],[1,2,5],[1,7],[2,6]]

共性

两题本质都是 回溯 + 排序剪枝，框架完全一样：

1. 先排序：排序后才能剪枝（candidates[i] > 剩余target 直接 break），也才方便去重。
2. 用 start 索引控制"只能往后选"：递归进入下一层时，只能从当前索引往后遍历，不能往回选。这一步是为了避免出现顺序不同但内容相同的组合（比如 [2,3] 和 [3,2] 被当成两个组合）。这一点两题都需要，因为解决的是"组合 vs 排列"问题，跟"能不能重复使用元素"无关。
3. 回溯三部曲：选择当前数 → 递归 → 撤销选择。

核心差异：递归时传的起始索引不同

• I（可重复使用）：递归调用时传 i，因为当前这个数还可以继续被选。
• II（每个数只能用一次）：递归调用时传 i + 1，因为这个数已经"用掉"了。

实现对比

I

...
for (int i = start; i < candidates.length; i++) {
    if (candidates[i] > remain) break; // 排序后剪枝
 
    path.add(candidates[i]);
    // 关键：传 i，因为当前数字可以重复使用
    backtrack(candidates, remain - candidates[i], i, path, result);
    path.remove(path.size() - 1);
}
...

II

for (int i = start; i < candidates.length; i++) {
    if (candidates[i] > remain) break; // 排序后剪枝
 
    // 关键：同一层跳过重复值，避免重复组合
    if (i > start && candidates[i] == candidates[i - 1]) continue;
 
    path.add(candidates[i]);
    // 关键：传 i + 1，因为当前数字只能用一次
    backtrack(candidates, remain - candidates[i], i + 1, path, result);
    path.remove(path.size() - 1);
}

两版代码之间只有 3 处不同（已在注释中标出）：

1. 递归调用传 i 还是 i + 1；
2. 是否需要"同层跳过重复值"这行判断；
3. （由此引出的）for 循环里 i > start 这个去重条件本身。

为什么组合总和 II 需要"跳过同层重复值"，而组合总和 I 不需要？

这是最容易搞混的点，原因如下：

• 组合总和 I 中 candidates 本身没有重复元素，所以同一层 for 循环里不可能出现两个数值相同的分支，天然不存在"数值重复"导致的重复组合。它唯一要防的重复是"顺序不同"，而这已经被 start 索引机制解决了。

• 组合总和 II 中 candidates 本身有重复元素（比如 [1,1,2,5,6,7,10]，排序后）。如果不加处理，同一层 for 循环中 i=0 选第一个 1、i=1 选第二个 1，会各自展开出一模一样的子树，导致结果集里出现两份完全相同的组合 [1,7]。所以要加：

  if (i > start && candidates[i] == candidates[i - 1]) continue;

  这句话的含义是："同一层（同一次 for 循环内）如果当前值和前一个值相同，就跳过"——但同一条路径往深处走（也就是不同层）时用两个值相同的数是允许的，因为它们是数组里不同位置的两个元素，各自只被用了一次（比如例子里的 [1,1,6] 就是合法答案，用了两个不同位置的 1）。

一句话总结

两题共享"排序 + start 索引只能往后走"的骨架，解决的是组合顺序去重问题； 区别仅在于：能否重复选同一个数（决定递归传 i 还是 i+1）和 candidates 是否本身有重复值（决定是否需要"同层跳过重复值"）。