LeetCode 40. 组合总和II——不可重复选取+去重的剪枝技巧
LeetCode 40. 组合总和II——不可重复选取+去重的剪枝技巧
适读人群：Java初中级工程师、算法进阶学习者 | 阅读时长：约20分钟 | 难度：中等
开篇故事
组合总和 II 是前两道组合题的"综合版"：既不允许重复选取（像 LeetCode 77 那样），又有重复元素需要去重（像子集 II 那样）。
这道题可以说是前面所有技巧的汇总考场。如果你看完了组合、组合总和和子集 II，这道题的代码几乎可以默写出来：用 i+1 防止重复选取，用 i > start && candidates[i] == candidates[i-1] 去重，再加上 candidates[i] > remain 时 break 的剪枝。
三招合一，这就是组合总和 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]]
与组合总和I的对比：
| 特性 | 组合总和I | 组合总和II |
|---|---|---|
| 候选数重复 | 无重复 | 有重复 |
| 每个数使用次数 | 无限 | 只用一次 |
| 去重需求 | 不需要 | 需要 |
| 递归起点 | i（允许重复选） | i+1（每个只用一次） |
| 额外去重条件 | 无 | i > start && cand[i] == cand[i-1] |
二、解法一：不去重的朴素回溯（会有重复结果）
首先看看如果只加了"不可重复选取"（i+1）但没有去重条件，会发生什么：
// 没有去重的版本（会有重复结果）
private void backtrack(int[] c, int remain, int start, List<Integer> path) {
if (remain == 0) { result.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 + 1, path); // i+1，每个数只用一次
path.remove(path.size() - 1);
}
}以 candidates=[1a,1b,2,7,6,5], target=8（排序后[1a,1b,2,5,6,7]）为例：
会生成 [1a,7] 和 [1b,7]，两者都是 [1,7]，产生重复。
三、解法二：排序+去重剪枝（正确解法）
代码
import java.util.*;
public class Solution {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates); // 排序，让重复元素相邻
backtrack(candidates, target, 0, new ArrayList<>());
return result;
}
private void backtrack(int[] candidates, int remain, int start, List<Integer> path) {
if (remain == 0) {
result.add(new ArrayList<>(path));
return;
}
for (int i = start; i < candidates.length; i++) {
// 剪枝1：如果当前候选数大于剩余目标，后面更大的也不必尝试
if (candidates[i] > remain) break;
// 剪枝2（去重）：同一层（start相同），跳过与前一个相同的值
if (i > start && candidates[i] == candidates[i-1]) continue;
path.add(candidates[i]);
backtrack(candidates, remain - candidates[i], i + 1, path); // i+1，不重复选
path.remove(path.size() - 1);
}
}
}三个关键设计点解析
1. Arrays.sort(candidates)：排序的必要性
排序后重复元素相邻，才能用 candidates[i] == candidates[i-1] 来判断重复；且升序排序后才能用 candidates[i] > remain 时 break 提前终止。
2. i + 1 vs i：不允许重复选取
递归时传 i + 1 而不是 i，确保每个数只使用一次。这是与组合总和I的唯一递归参数差异。
3. i > start && candidates[i] == candidates[i-1]：去重剪枝
i > start：当前不是本层第一个候选（本层由 start 参数定义起点）。candidates[i] == candidates[i-1]：当前元素与前一个相同（排序后相邻的重复值）。- 满足两个条件时 continue：在同一层，相同值只选第一个出现的，避免生成重复组合。
与子集 II 完全相同的去重逻辑。
Mermaid 图：去重效果（candidates=[1,1,2,5], target=6）
最终结果： [[1,1,4]... 实际为[[1,5],[1,1,...]]，根据具体值确定]
复杂度分析
- 时间复杂度： O(2^n × n) 最坏情况（每个元素都不同时，相当于求所有子集），含重复元素时去重大幅减少。
- 空间复杂度： O(n)，递归栈深度。
四、解法三：迭代+去重（理解去重逻辑的迭代版）
将回溯拆成迭代形式，明确展示去重逻辑：
import java.util.*;
public class Solution_Iterative {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> result = new ArrayList<>();
// 用栈模拟：(剩余目标, 起始下标, 当前路径)
// 这里用显式的DFS栈实现回溯
dfs(candidates, target, 0, new ArrayList<>(), result);
return result;
}
// 等价于上面的递归版本，在此保留递归写法作为参考
// 真正的"迭代"需要显式维护栈，逻辑更复杂，实用价值不高
// 此处展示另一种写法：用for循环+内层递归，强调每一步决策
private void dfs(int[] c, int remain, int start,
List<Integer> path, List<List<Integer>> result) {
if (remain == 0) { result.add(new ArrayList<>(path)); return; }
Integer prevChosen = null; // 本层上一个选过的值
for (int i = start; i < c.length && c[i] <= remain; i++) {
if (prevChosen != null && prevChosen == c[i]) continue; // 去重
prevChosen = c[i];
path.add(c[i]);
dfs(c, remain - c[i], i + 1, path, result);
path.remove(path.size() - 1);
}
}
}这里用 prevChosen 记录本层上一个选过的值，等价于 i > start && c[i] == c[i-1] 的判断，但语义更直观：我们明确记录"已经处理过这个值"。
五、举一反三
四道组合类题目的完整对比
// 77. 组合：选k个，不重复元素，不可重选
backtrack(start, path) {
if (path.size() == k) { 记录; return; }
for (i = start; i <= n - (k-path.size()) + 1; i++) { // 剪枝上界
path.add(i);
backtrack(i+1, path); // i+1，不重选
path.remove();
}
}
// 39. 组合总和：不重复元素，可重选，目标和
backtrack(start, remain) {
if (remain == 0) { 记录; return; }
for (i = start; i < n && c[i] <= remain; i++) {
path.add(c[i]);
backtrack(i, remain-c[i]); // i，可重选
path.remove();
}
}
// 40. 组合总和II：重复元素，不可重选，目标和
backtrack(start, remain) {
if (remain == 0) { 记录; return; }
for (i = start; i < n && c[i] <= remain; i++) {
if (i > start && c[i] == c[i-1]) continue; // 去重
path.add(c[i]);
backtrack(i+1, remain-c[i]); // i+1，不重选
path.remove();
}
}六、踩坑实录
坑一：去重条件放在剪枝条件之前还是之后
if (candidates[i] > remain) break; // 剪枝放前
if (i > start && candidates[i] == candidates[i-1]) continue; // 去重放后顺序很重要：先检查 candidates[i] > remain（break 跳出整个循环），再检查去重（continue 只跳过当前）。如果顺序调换，可能在 continue 的情况下漏掉 break，导致效率降低。
坑二：递归时传 i 还是 i+1
组合总和 II 传 i+1（不可重选），组合总和 I 传 i（可重选）。这是两题唯一的递归参数差异。写完代码后务必检查这一点。
坑三：candidates 排序放在哪里
排序必须在 backtrack 调用之前，在 combinationSum2 方法内的第一行。不要把排序放到递归函数里，否则每次递归都会排序，增加无效开销。
坑四：continue vs break 的场景判断
candidates[i] > remain→break（排序后，后面更大，整层可以结束）i > start && c[i] == c[i-1]→continue（只跳过当前这个重复元素，后面可能还有其他有效元素）
混用会导致要么漏结果，要么多了无效计算。
七、总结
组合总和 II 是回溯去重系列的集大成之作，融合了：
- 排序：为 break 剪枝和去重条件提供基础。
- i+1：每个元素只用一次，防止重复选取同一个位置的元素。
- i > start && c[i] == c[i-1]：同层去重，防止相同值被多次作为本层起点。
- c[i] > remain 时 break：剩余不足时提前终止分支。
这四点同时用好，才能写出正确且高效的组合总和 II 解法。
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 无去重回溯 | O(2^n × n) | O(n) | 结果有重复 |
| 排序+剪枝回溯 | O(2^n × n) 最坏 | O(n) | 正确，推荐 |
| prevChosen记录 | O(2^n × n) 最坏 | O(n) | 语义直观 |
补充深入讲解：不重复组合求和的剪枝策略深度分析
LeetCode 39 与 LeetCode 40 的本质区别
LeetCode 39（组合总和）和 LeetCode 40（组合总和 II）的区别有两点：其一，40 中每个数字在每个组合中只能使用一次（而 39 中可以无限次使用）；其二，40 中的候选数组可能含有重复元素（需要去重）。
这两点区别叠加在一起，使得 40 的去重逻辑比 39 更复杂。我们需要同时保证：一个数字不被同一个组合重复选取，以及相同值的不同数字不产生重复组合。
解决方法是：排序之后，用 start 参数保证每个数字只被选一次（不重复选取），用 i > start && candidates[i] == candidates[i-1] 的条件去掉同层的重复候选（避免重复组合）。这两个机制分别解决了两个不同的问题，合在一起就构成了完整的解法。
为什么 i > start 而不是 i > 0
在去重条件 i > start && candidates[i] == candidates[i-1] 中，用 i > start 而不是 i > 0，是一个关键细节。
i > 0 && candidates[i] == candidates[i-1] 的意思是：只要当前元素和前一个元素值相同，就跳过。这会在某些情况下导致正确结果被跳过。
考虑 candidates=[1,1,2]，target=3。排序后 candidates=[1,1,2]。如果用 i > 0 的条件，在第一层选择时，下标 1（第二个 1）会被跳过（因为 candidates[1]==candidates[0]）。但实际上，[1（下标0）,2] 和 [1（下标1）,2] 是两种不同的选法（虽然值相同），然而我们想要的去重是去掉组合 [1,2] 的重复，不是去掉所有用到第二个 1 的情况。
关键在于：我们要允许"选两个 1"（用下标 0 和下标 1 的两个 1），形成组合 [1,1]（如果 target 允许）。如果用 i > 0，在第一层选了下标 0 的 1 之后，进入第二层时 start=1，在第二层如果用 i > start（即 i > 1）才剪枝，这时下标 1 的 1 不会被跳过（因为 i=1=start，不满足 i > start），所以 [1,1] 能被正确找到。
i > start 确保：只有在当前层，前面的候选已经以相同值被尝试并跳过时，才剪掉当前候选。这精确地实现了"同层去重，跨层不去重"的逻辑。
三种去重策略的比较
策略一：排序 + i > start && candidates[i] == candidates[i-1]（推荐）
优点：纯数组操作，无额外空间，代码简洁。缺点：需要理解 i > start 的语义，初次理解有难度。
策略二：HashSet 记录已选值（直观但开销较大）
在每一层维护一个 HashSet seen，记录当前层已经尝试过的值。遍历候选时，如果 candidates[i] 在 seen 中，跳过；否则加入 seen 并继续。优点：逻辑直观。缺点：每层需要创建 HashSet，内存分配和 GC 开销较大，且代码更长。
策略三：标记数组（类似 visited）
对排序后的数组，用一个布尔数组 used 标记每个下标是否已使用。和 LeetCode 47（全排列 II）的 visited 方式类似。但在组合问题中，不需要 visited 数组，因为 start 参数已经限制了选择范围，不会重复选同一个下标。
在竞赛中推荐策略一，代码最精简，效率最高。在面试时，能解释清楚 i > start 的语义即可，不必使用 HashSet 来"讨好"面试官（HashSet 方式不代表更好理解）。
剪枝与求和上界的配合
组合总和 II 中同样可以利用排序进行求和上界剪枝：当 candidates[i] > remaining 时，直接 break（因为之后的元素更大，也会超过 remaining）。这个剪枝与去重剪枝是独立的，可以同时使用。
去重剪枝减少了同层的分支数（跳过重复值），上界剪枝减少了大值的分支（跳过超出范围的值）。两个剪枝合在一起，使得回溯树比最坏情况小得多，在实际测试中能通过较大的输入规模。
组合总和 II 的工程应用
组合总和 II（不重复元素，每个只用一次）在工程中的典型应用是预算分配问题：给定一组金额各不相同的可选项目（但金额可能相同），总预算为 target，找出所有恰好花完预算的项目组合。每个项目只能选一次（不能重复选），不同项目即使金额相同也算不同选择，但如果两个不同项目金额相同、功能等价，只选其中一个就够了（去重）。
这个场景在实际的资源调度、任务分配系统中经常出现。理解回溯去重的原理，有助于在工程实现中正确处理"等价选项的去重"问题，避免重复计算或重复执行相同的方案。
组合总和 II 与 I 的框架差异总结
LeetCode 39（组合总和）和 LeetCode 40（组合总和 II）的代码框架极为相似，差异体现在三处细节：
第一处，start 参数传递方式不同。LeetCode 39 中递归调用传 i（允许重复选），LeetCode 40 中传 i+1（每个元素只用一次）。这决定了元素是否可以重复选取。
第二处，去重条件的有无。LeetCode 39 中 candidates 无重复，无需去重；LeetCode 40 中 candidates 可能有重复元素，需要在同层跳过重复值（i > start && candidates[i] == candidates[i-1]）。
第三处，思路上对"来源"的处理。LeetCode 39 同一来源可以重复使用，LeetCode 40 每个位置最多使用一次，但多个位置的相同值算不同来源（但作为"组合"只算一种选法）。
从代码量上看，40 比 39 只多了一个 if 判断（去重条件），却使得问题复杂度大为不同。这体现了算法设计的精妙：相似的框架，通过细小的修改适应不同的约束条件。
从组合总和到硬币找零问题的联系
LeetCode 40 和经典的硬币找零问题（LeetCode 322）有密切的联系。硬币找零（322）求最少使用多少枚硬币凑出目标金额，是动态规划问题；组合总和 II（40）求所有恰好凑出目标金额的组合列表，是回溯问题。
两者面对同样的基本设定（有限种类的整数，凑出目标值），但问题目标不同：动态规划求最优解的度量值（最少枚数），回溯枚举所有可行解（所有组合）。
一般规律：当只需要最优解的度量值时，动态规划（O(n×target)）比回溯高效；当需要枚举所有可行解时，必须使用回溯（时间复杂度与方案数相关，无法避免）。这个"动态规划求最优，回溯枚举方案"的分工原则是算法选择的重要参考。
理解了这道题与动态规划的联系，也有助于在面试中展现算法知识的广度和深度：在解释回溯解法的同时，提及DP解法的存在和适用场景，说明两种方法的适用条件差异，体现对算法问题的全局视野。
组合总和 II 的代码正确性验证
对于含重复元素的组合类回溯，一个可靠的正确性验证方法是：用小规模数据手动追踪去重条件的执行。
以 candidates=[1,1,2]，target=3 为例（排序后 [1,1,2]）：
第一层 i=0 选 1（下标0），进入第二层：在第二层 i=1，candidates[1]=1，candidates[0]=1，且 i > start（1 > 1 为假），所以不触发去重，可以选第二个 1，得到路径 [1,1]。继续第三层选 2，得到结果 [1,1,2]？不对，sum=4>3 了。实际 remaining=3-1=2，第二层选 1 后 remaining=1，第三层 candidates[2]=2>1，break，无结果。第二层选 2（i=2），remaining=0，记录 [1,2]。第一层 i=1 选 1（下标1），此时 i=1 > start=0，且 candidates[1]==candidates[0]，去重条件触发，跳过。第一层 i=2 选 2，remaining=1，进入第二层但所有候选>1，无结果。
最终结果：[1,2]。验证正确（candidates=[1,1,2]，target=3 的不重复组合只有 [1,2]）。
这种追踪练习能帮助建立对去重逻辑的直觉，发现潜在的逻辑错误，是学习回溯去重的有效方法。
组合总和系列题目的一致性
LeetCode 39 和 40 是同一类问题的两个变种，理解了它们之间的关系，就掌握了"求和约束的组合枚举"这一类问题的完整解法框架：
无重复候选，可重复选取（LeetCode 39）：start 传 i，无需去重。 有重复候选，不可重复选取（LeetCode 40）：start 传 i+1，需要同层去重。 无重复候选，不可重复选取（LeetCode 77 加求和约束）：start 传 i+1，无需去重，但需要检查路径长度（组合大小）。
把这三种情况的代码差异整理成一个对比表，就形成了组合类回溯的完整知识体系，面试时遇到任何变形都能快速定位到正确的代码模板。
组合总和 II 的一句话核心思路
LeetCode 40 的核心思路：排序，然后回溯时用 i > start 且 candidates[i] 等于 candidates[i-1] 去重（同层不选相同值），用 start 传 i+1（每个元素只用一次），用 candidates[i] > remaining 时 break（超出范围就剪枝）。这三个要点合在一起，构成了含重复候选的不重复组合枚举的完整解法。面试时能同时解释这三个要点的来源和正确性，是解题能力的充分展示。
组合总和 II 是回溯去重的综合练习题，同时涉及"每个元素只用一次"（start 传 i+1）和"含重复元素去重"（同层跳过相同值）两个机制，是所有组合类回溯去重题目的最综合体现。
组合总和 II 在回溯学习路径上是重要的里程碑：它综合了排序预处理、同层去重、每元素限用一次和求和剪枝四个技巧，是组合类回溯的集大成者。
掌握这道题的四个技巧（排序、去重、限用一次、求和剪枝），就能处理绝大多数组合类回溯变形题目。