子集 II 如何用回溯去重？为什么要用同层去重？

简化版

子集 II 的输入包含重复元素，先排序，再用回溯枚举子集；每一层循环里如果 i > start && nums[i] == nums[i - 1]，说明同层已经用过相同值作为本位置选择，直接跳过。这样既保留不同层的重复值组合，又避免重复子集。

详细版

普通子集题每个元素只有选或不选，直接从 start 往后枚举即可。子集 II 的难点是重复元素会生成重复答案，例如 [1,2,2] 中，第一个 2 和第二个 2 单独组成的 [2] 值相同，答案只能保留一次。

解决方式是先排序，让相同元素相邻；然后在同一递归层跳过重复候选：if (i > start && nums[i] == nums[i - 1]) continue。注意条件是 i > start，不是 i > 0。因为同一层不能重复选相同值，但下一层允许继续选相同值来形成 [2,2]。

回溯过程中每到一个节点都收集一次当前 path，因为任何前缀都是一个合法子集。时间复杂度主要由输出规模决定，最多有 2^n 个子集，复制答案还要乘路径长度。

完整版教学

一、为什么重复元素会制造重复子集

子集看的是“选出来的值集合”，不是原数组下标。如果数组是 [1,2,2]，两个 2 的下标不同，但子集 [2] 只应该出现一次。若不去重，回溯会分别选择第一个 2 和第二个 2，得到两个值完全一样的 [2]。

先把输入排序成 [1,2,2]，重复值靠在一起，重复来源就变得可观察。去重不是删除所有重复值，因为 [2,2] 是合法子集；真正要删除的是“同一层用同一个值开启两条等价分支”。

第 0 层选择：
选 nums[1]=2 -> 生成 [2], [2,2]
选 nums[2]=2 -> 又生成 [2]
同层第二个 2 应跳过

二、同层去重和同枝保留的区别

回溯树里有两个维度：横向是同一层的候选，纵向是一条路径继续往下选。子集 II 的规则是横向去重、纵向不去重。也就是说，同一层不能让两个相同的值分别作为“本层第一个选择”；但如果路径里已经选了一个 2，下一层还可以再选另一个 2，形成 [2,2]。

这就是 i > start 的意义。i == start 表示当前层第一个候选，无论是否等于前一个数组元素，都应该允许选择；i > start 且等于前一个，才说明同层重复。

记忆钩子：子集 II 去重记成“横向同层跳重复，纵向同枝可继续”，条件就是 i > start。

三、代码模板

每到一个递归节点都先收集 path，然后从 start 开始枚举后续元素。选择一个元素后，下一层从 i + 1 开始，因为每个数组位置最多使用一次。

List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), res);
    return res;
}

void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) continue;
        path.add(nums[i]);
        backtrack(nums, i + 1, path, res);
        path.remove(path.size() - 1);
    }
}

这段代码里，start 定义了候选范围，path 定义了当前子集，res.add(new ArrayList<>(path)) 必须复制快照，不能直接存 path 引用。

四、用数字例子走一遍

输入 [1,2,2] 排序后不变。根节点先收集 []；第 0 层选 1，进入下一层收集 [1]；再选第一个 2 收集 [1,2]，继续选第二个 2 收集 [1,2,2]。

回到 [1] 所在层时，循环来到第二个 2，此时 i > start 且 nums[i] == nums[i-1]，跳过，避免重复 [1,2]。回到根节点后，选第一个 2 得到 [2]、[2,2]；根节点再看到第二个 2，也同层跳过。

递归层	path	候选	处理
0	`[]`	`1,2,2`	第二个 2 同层跳过
1	`[1]`	`2,2`	第二个 2 同层跳过
1	`[2]`	`2`	允许形成 `[2,2]`

五、和全排列 II 的去重条件不同

子集和全排列都要处理重复元素，但条件不一样。子集使用 start 控制候选范围，不需要 used[]；全排列每层都可能从头扫描所有元素，需要 used[] 判断哪个下标已经在路径里。

题型	候选范围	去重条件	原因
子集 II	`i >= start`	`i > start && nums[i]==nums[i-1]`	同层重复值只开一条分支
全排列 II	全数组扫描	`i>0 && nums[i]==nums[i-1] && !used[i-1]`	前一个相同值未使用时跳过

面试里要把“同层去重”讲清楚，不要机械背条件。条件背错最常见的后果是漏掉 [2,2] 或重复输出 [2]。

六、常见误区与追问

误区：把重复元素先用 Set 去掉。 这样会丢掉合法答案 [2,2]，重复值不是完全无用。
误区：条件写成 i > 0。 这会把不同层的重复值也跳掉，导致 [2,2] 缺失。
误区：收集答案时不复制 path。 path 后续会被撤销修改，直接保存引用会导致答案全变空或相同。
追问：为什么要先排序？ 排序让相同值相邻，同层去重才能只比较前一个元素。
追问：复杂度是多少？ 最坏仍是 O(n * 2^n) 的输出成本，去重只能减少重复分支，不能改变指数级输出上界。
追问：能用选/不选写法吗？ 可以，但处理重复段时要一次性跳过相同值，代码比 for 模板更绕。

七、加强记忆

子集 II 的核心是“排序后横向去重，纵向保留重复值”。start 控制每个元素最多用一次，i > start 识别同层重复候选。先收集当前路径，再枚举后续选择；只要记住同层跳重复、同枝可继续，就不会把 [2] 重复输出，也不会漏掉 [2,2]。

简化版

详细版