组合总和 II 如何处理每个元素只能用一次和重复候选？

简化版

组合总和 II 先排序，再用 start 回溯枚举候选；因为每个元素只能用一次，递归传 i + 1；因为输入可能有重复值，同一层遇到 i > start && candidates[i] == candidates[i - 1] 要跳过。remain == 0 收集答案，candidates[i] > remain 时直接 break 剪枝。

详细版

这题和组合总和 I 的关键区别有两个：候选数组可能有重复值，但答案不能重复；每个数组位置最多只能使用一次。因此选择 candidates[i] 后，下一层必须从 i + 1 开始，不能继续传 i。

去重必须发生在同一递归层。排序后，相同值相邻；如果本层已经用过一个值作为当前位置选择，再用后面的相同值会生成重复组合，应跳过。条件是 i > start && candidates[i] == candidates[i - 1]。

由于候选值都是正数，排序后如果当前值已经大于剩余目标 remain，后面的值只会更大，可以 break 剪掉整段分支。整体复杂度仍是指数级，剪枝和去重能显著减少实际搜索。

完整版教学

一、题目真正考两个约束

组合总和 II 给定 candidates = [10,1,2,7,6,1,5]、target = 8，答案是 [[1,1,6],[1,2,5],[1,7],[2,6]]。这里的两个 1 来自不同下标，所以 [1,1,6] 合法；但 [1,7] 不能因为选择了“第一个 1”或“第二个 1”而出现两次。

因此本题不是简单的“组合总和 I 改成不能重复选”。它同时要求：数组位置只能用一次、相同值导致的重复组合要去掉。前者由 i + 1 解决，后者由排序后的同层去重解决。

排序后：[1,1,2,5,6,7,10]
target=8
同层第一个 1 可以选
同层第二个 1 若作为同一位置选择，会重复，跳过
但选了第一个 1 后，下一层仍可选第二个 1，形成 [1,1,6]

二、为什么递归传 i + 1

每个元素只能使用一次，说的是“每个下标最多用一次”。当你在当前层选择了下标 i，下一层候选只能从 i + 1 开始，否则会再次选择同一个位置。这个点和组合总和 I 正好相反，组合总和 I 可重复使用同一个数，所以传 i。

对比例子：[2,3,6,7] target=7 中，组合总和 I 可以选 [2,2,3]，因为 2 能重复用；组合总和 II 中如果数组只有一个 2，就不能重复选择它。

题目	选择后下一层 start	含义
组合总和 I	`i`	当前数还能再用
组合总和 II	`i + 1`	当前下标已用过

三、同层去重为什么不能写错

排序后重复值相邻，同层去重条件是 i > start && candidates[i] == candidates[i - 1]。i > start 表示这不是当前层第一个候选；如果它和前一个候选值相同，那么前一个候选已经代表这一层的这个值开过分支，再开一次只会重复。

但如果 i == start，即使它等于前一个数组值，也不能跳过。因为那说明前一个相同值可能是在上一层被选进路径了，当前层继续选择它是合法的 [1,1,...]。

记忆钩子：组合总和 II 去重只跳“兄弟节点”的重复值，不跳“父子路径”里的重复值。

四、代码模板

模板里有三个关键动作：排序、同层去重、超过剩余目标后 break。它们分别解决“重复相邻”“重复答案”“正数剪枝”。

List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);
    List<List<Integer>> res = new ArrayList<>();
    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) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i < c.length; i++) {
        if (i > start && c[i] == c[i - 1]) continue;
        if (c[i] > remain) break;
        path.add(c[i]);
        backtrack(c, remain - c[i], i + 1, path, res);
        path.remove(path.size() - 1);
    }
}

注意 remain 是递减状态，避免每次重新求路径和；path 是共享可变对象，收集答案时必须复制。

五、手推样例看去重位置

排序后 [1,1,2,5,6,7,10]。根层选第一个 1 后，下一层从第二个 1 开始，可以继续选第二个 1，得到路径 [1,1]，再选 6 命中 [1,1,6]。

回到根层后，循环来到第二个 1，此时 i > start 且值等于前一个 1，跳过。否则它会再次生成 [1,2,5]、[1,7] 等重复答案。

根层：
  选第一个 1 -> 允许继续选第二个 1
  跳过第二个 1 -> 因为同层第一个 1 已经代表值 1
  选 2 -> 后续找 6

这个例子能解释为什么去重条件不能放在递归入口统一处理，而要放在当前层的 for 循环里。

六、常见误区与追问

误区：递归继续传 i。 这会允许同一个下标重复使用，变成组合总和 I。
误区：看到重复值就全部跳过。 [1,1,6] 需要两个 1，不能删除所有重复值。
误区：去重条件写成 i > 0。 会误伤不同层的重复选择，导致合法答案缺失。
追问：为什么可以 break 而不是 continue？ 排序后当前值已大于 remain，后续值更大，整段都不可能命中。
追问：如果候选里有负数还能这样剪枝吗？ 不能，remain 不再单调下降，排序后的 break 也不安全。
追问：和子集 II 的去重一样吗？ 核心同为同层去重，但组合总和 II 多了 remain 目标和超过目标剪枝。

七、加强记忆

组合总和 II 记成“只能用一次传 i+1，重复候选同层跳，正数排序可 break”。i + 1 解决下标复用，i > start 解决兄弟节点重复，c[i] > remain 解决无效大分支。把这三个点分清，代码就不会和组合总和 I 混在一起。

简化版

详细版