import java.util.*;

public class Solution_PostDedup {
    private Set<List<Integer>> resultSet = new HashSet<>();
    
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backtrack(nums, 0, new ArrayList<>());
        return new ArrayList<>(resultSet);
    }
    
    private void backtrack(int[] nums, int start, List<Integer> path) {
        resultSet.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, i + 1, path);
            path.remove(path.size() - 1);
        }
    }
}

缺点： 生成所有（含重复）子集，用 HashSet 过滤。比排序+剪枝慢，且 List 的 hashCode 计算开销大。

复杂度： 时间 O(2^n × n)，空间 O(2^n × n)（Set 存储所有子集）。

三、解法二：排序+剪枝（关键解法）

思路

去重条件： i > start && nums[i] == nums[i-1]

i > start：表示当前 i 不是"本层"的第一个候选。start 是本层的起始下标，i == start 时是本层第一次选这个值，允许；i > start 时，nums[i] 与 nums[i-1] 相同，说明本层已经处理过相同值，跳过。
nums[i] == nums[i-1]：当前元素与前一个元素相同（排序后相邻）。

为什么是 i > start 而不是 i > 0？

假设 nums = [2,2,3]，start = 0：

i=0，选 nums[0]=2：递归处理 [2,3]
i=1，nums[1]==nums[0]=2，且 i=1 > start=0：跳过（本层已经用第一个2处理了，不再用第二个2重复处理）
i=2，选 nums[2]=3：递归处理 []

但在下一层（start=1，处理 [2,3] 中的子集）：

i=1，选 nums[1]=2：合法！（本层第一次选这个2）
i=2，选 nums[2]=3

所以当 start=1，i=1 时，i == start，不满足 i > start，允许选取。这就是用 i > start 而不是 i > 0 的原因：不同层的"起点"不同，每层的第一个候选位置都是 start，i > start 精确地定义了"本层已经有过这个值了"。

代码

import java.util.*;

public class Solution {
    private List<List<Integer>> result = new ArrayList<>();
    
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums); // 必须排序，使相同元素相邻
        backtrack(nums, 0, new ArrayList<>());
        return result;
    }
    
    private void backtrack(int[] nums, int start, List<Integer> path) {
        // 每到一个节点就记录（包括空集和所有中间路径）
        result.add(new ArrayList<>(path));
        
        for (int i = start; i < nums.length; i++) {
            // 去重剪枝：同层跳过重复值（注意是 i > start，不是 i > 0）
            if (i > start && nums[i] == nums[i-1]) continue;
            
            path.add(nums[i]);
            backtrack(nums, i + 1, path);
            path.remove(path.size() - 1);
        }
    }
}

Mermaid 图：以 [1,2,2] 为例的递归树

生成的子集： [], [1], [1,2], [1,2,2], [2], [2,2] — 共6个，无重复。

复杂度分析

时间复杂度： O(n × 2^n) 最坏情况（无重复时），有重复时剪枝后实际更快。排序 O(n log n)。
空间复杂度： O(n)，递归栈深度。

四、解法三：迭代+跳过重复（扩展解法二的迭代思路）

思路

在子集 I 的迭代方法基础上，加入去重逻辑：当遇到重复元素时，只对"上一轮新加入的子集"再添加这个重复元素，而不是对所有已有子集添加。

图示：

初始: result = [[]]
加入1: 对所有已有子集加1 → result = [[], [1]]
加入第一个2: 对所有已有子集加2 → result = [[], [1], [2], [1,2]]
             （新增了2个子集：[2]和[1,2]，这轮新增的有2个）
加入第二个2（重复！）: 只对上一轮新增的子集加2
             上一轮新增: [2], [1,2]
             新增: [2,2], [1,2,2]
             result = [[], [1], [2], [1,2], [2,2], [1,2,2]]

代码

import java.util.*;

public class Solution_Iterative {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        
        int prevSize = 0; // 上一轮新增前的结果集大小
        
        for (int i = 0; i < nums.length; i++) {
            int startIdx;
            if (i > 0 && nums[i] == nums[i-1]) {
                // 重复元素：只对上一轮新增的子集加这个元素
                startIdx = prevSize;
            } else {
                // 新元素：对所有已有子集加这个元素
                startIdx = 0;
            }
            
            prevSize = result.size(); // 记录本轮开始前的大小（即本轮新增前）
            
            int size = result.size();
            for (int j = startIdx; j < size; j++) {
                List<Integer> newSubset = new ArrayList<>(result.get(j));
                newSubset.add(nums[i]);
                result.add(newSubset);
            }
        }
        
        return result;
    }
}

执行过程：

初始：result = [[]]，prevSize = 0
i=0，nums[0]=1，新元素，startIdx=0，prevSize=1（当前size），对所有[startIdx,0]加1 → result=[[], [1]]
等一下，这里的 prevSize 更新顺序要仔细：

// 正确的执行顺序（修正版代码）：
for (int i = 0; i < nums.length; i++) {
    int size = result.size();
    int startIdx = (i > 0 && nums[i] == nums[i-1]) ? prevSize : 0;
    prevSize = size; // 记录本轮开始时的size（本轮结束时，这些就是"上一轮新增"的起点）
    for (int j = startIdx; j < size; j++) {
        List<Integer> ns = new ArrayList<>(result.get(j));
        ns.add(nums[i]);
        result.add(ns);
    }
}

复杂度分析

时间复杂度： O(n × 2^n)，最多 2^n 个子集，每个复制需要 O(n)。
空间复杂度： O(n × 2^n)，同时存储所有子集。

五、举一反三

回溯去重四道题的统一对比

题目	剪枝条件	原因
子集II（本题）	`i > start && nums[i] == nums[i-1]`	同层（start限定层）跳过重复
组合总和II（#594）	`i > start && nums[i] == nums[i-1]`	同上，组合也是"有序子集"
全排列II（#589）	`i > 0 && nums[i] == nums[i-1] && !visited[i-1]`	排列不限制起始位置，用visited区分层
分割回文串（#595）	无需去重（无重复字母场景）	不适用

关键记忆：

子集/组合（从前到后选）：用 i > start（start是本层起点）
排列（从全集中选）：用 !visited[i-1]（无固定start，用visited区分同层/深层）

六、踩坑实录

坑一：用 i > 0 而不是 i > start

// 错误：在深层递归中，即使i==start也会被跳过
if (i > 0 && nums[i] == nums[i-1]) continue;

// 正确：只在同层（i > start）时跳过重复
if (i > start && nums[i] == nums[i-1]) continue;

用 i > 0 的问题：考虑 nums=[1,2,2]，当 start=1（处理第二层子集 [2,?] 时），i=1（nums[1]=2 是本层第一个候选），此时 i > 0 且 nums[1] == nums[0]（nums[0]=1，不等），好像还好。但考虑 nums=[2,2,3]，start=1 时 i=1，i > 0 && nums[1] == nums[0]（2==2）→ 跳过！但这是合法的，因为 i=1=start，是本层第一个2，不应该跳过。

坑二：忘记在 backtrack 开头记录当前 path

子集问题的特点是每个节点（包括中间节点）都是合法的子集，所以 result.add(new ArrayList<>(path)) 要在 for 循环之前执行，不能放在循环内部或只在叶子节点执行。

坑三：迭代方法中 prevSize 的更新顺序

prevSize 代表"上一轮新增之前的结果集大小"，必须在每轮开始时（扩展之前）更新。如果放在扩展之后更新，会错误地将本轮新增的子集也计入"上一轮"。

七、总结

子集 II 是掌握"回溯去重统一框架"的关键题目。核心去重条件 i > start && nums[i] == nums[i-1] 精确地定义了"同层重复跳过"，而不影响"不同层的相同值"。

对比全排列 II 的去重条件 !visited[i-1]，两者解决的都是"同层重复导致的重复结果"问题，只是定义"同层"的方式不同：子集/组合用 start 参数定义层，排列用 visited 状态区分层。

解法	时间复杂度	空间复杂度	推荐
事后Set去重	O(n × 2^n)	O(n × 2^n)	不推荐
排序+条件剪枝	O(n × 2^n)	O(n)	强烈推荐
迭代+跳过重复	O(n × 2^n)	O(n × 2^n)	理解辅助

补充深入讲解：含重复元素子集去重的系统分析

去重的根本问题：什么时候两个子集"相同"

子集是集合的概念，集合是无序且不重复的。但 LeetCode 90 的输入是数组（有序，可重复），输出是子集的列表。问题在于：含重复元素的数组，不同的"选取方式"可能产生相同内容的子集。

以 nums=[1,2,2] 为例，有两个值为 2 的元素（记为 2a 和 2b）。选 {1,2a} 和选 {1,2b} 产生的子集内容完全一样，都是 [1,2]，我们只想保留一个。去重的目标就是：对于每种"内容不同"的子集，只枚举一次。

排序之后，相同值的元素聚在一起。去重策略是：对于值相同的一批元素（比如有 k 个值为 x 的元素），我们只关心选了多少个 x（可以是 0,1,2,...,k 个），而不关心"选的是哪些 x"。这样就把"内容相同的多种选法"折叠成了"同一种选法"。

回溯去重条件 i > start && nums[i] == nums[i-1] 的精确含义

这个条件在子集去重和排列去重中都出现，但语义略有不同。

在子集回溯中，start 表示当前层可以选择的起始下标（保证子集中元素按下标递增顺序）。如果 i > start，说明下标 i 不是当前层的第一个候选；如果 nums[i] == nums[i-1]，说明当前候选和前一个候选值相同。

当 i > start 且 nums[i] == nums[i-1] 时，意味着：前一个候选 nums[i-1] 在当前层已经被跳过了（如果它被选了，那么递归进入更深层时，start 会大于 i-1，导致 i > start 不成立但另一层的逻辑来处理它）。跳过了 nums[i-1] 却选 nums[i]，等价于"选了一个与被跳过的值相同的元素"，这和"选了 nums[i-1]"产生的是相同内容的子集。因此跳过。

i > start 这个条件的作用是：只跳过"在当前层被跳过的重复值"，而不跳过"在上层已经被选进路径的值"。这保证了当 nums 中有连续多个相同值时，我们能正确地选 1 个、2 个……直到最多的所有个，而不是只能选 0 个或全选。

迭代去重方式的原理

迭代去重方式中，当遇到与前一个元素值相同的元素时，只在上一轮新增的子集（而非所有已有子集）的基础上扩展。这个策略的原理如下：

对于不重复的元素，每个新元素加入时，已有的所有子集都有"加入新元素"和"不加入新元素"两种扩展方式，各自产生一批新子集，两批合并得到新的子集列表。

对于重复的元素（与前一个相同），如果继续在所有已有子集的基础上扩展，会产生重复：因为"不包含前一个元素的子集加上当前元素"与"包含前一个元素的某个子集"内容相同。

因此，对于重复元素，只在"上一轮新增的子集"（即包含前一个相同元素的那批子集）的基础上扩展，而已有的其他子集保持不变。这样保证了对于 k 个相同值 x，子集中出现 0 个 x、1 个 x、2 个 x……直到 k 个 x 的情况都恰好被枚举一次。

多重集合子集计数的公式

对于含重复元素的数组，子集数量有精确的计算公式。如果数组中值 v1 出现 c1 次、值 v2 出现 c2 次……值 vm 出现 cm 次，则不同子集的总数是 (c1+1)×(c2+1)×...×(cm+1)。

对于 nums=[1,2,2,3]，1 出现 1 次（1+1=2 种选法：选 0 个或 1 个），2 出现 2 次（2+1=3 种选法：选 0、1、2 个），3 出现 1 次（2 种选法），共 2×3×2=12 个不同子集。

这个公式告诉我们：含重复元素的子集问题，实际上是一个"多维计数"问题——每种值独立地决定选几个，不同值的选择相互独立。去重算法的本质就是正确地实现这个多维独立枚举。

从子集到组合的联系

子集（LeetCode 90）和组合（LeetCode 40 组合总和II）的去重逻辑完全相同，这不是巧合。两者本质上都是"从含重复元素的集合中选取元素，产生不重复的组合"。区别在于：子集是枚举所有大小的组合（0 到 n 个元素），而 LeetCode 40 是枚举满足特定求和条件的组合。

去重的核心条件 i > start && nums[i] == nums[i-1] 在两道题中完全通用，只要理解了它的含义，就能在所有组合类回溯题中正确应用。这个条件是组合类回溯去重的"通用公式"，值得深刻理解并记牢。

含重复元素子集的完整枚举策略对比

含重复元素子集（LeetCode 90）的三种主要解法各有优劣，值得深入比较。

方法一是排序+回溯去重，代码简洁，时间空间效率最优，是面试首选。关键在于理解 i > start && nums[i] == nums[i-1] 这个去重条件，它保证了在决策树的同一层，相同值的候选只被第一个尝试，后续相同值被跳过，从而消除了重复子集。

方法二是迭代去重，逻辑直观但代码稍长。遇到与前一个元素值相同的元素时，只对上一轮新增的子集进行扩展（而非所有已有子集），保证了对相同值的不同数量选取（0个、1个、2个……）各自被枚举恰好一次。

方法三是位掩码+HashSet 去重，将每个子集转换为排序后的字符串或列表作为 HashSet 的键，自动去重。这种方法最直接，但 HashSet 的存储和查找开销较大，且需要额外 O(2^n × n) 的空间存储所有已生成子集。

在实际面试中，不需要知道所有三种方法，掌握方法一（回溯去重）就足够。关键是能清晰地解释去重条件的含义和原理，展示对回溯本质的理解，而不只是背下代码。

子集 II 与子集 I 的学习路径

建议按以下顺序学习：先学 LeetCode 78（无重复元素，三种方法），理解枚举的基本框架；再学 LeetCode 90（含重复元素，回溯去重），在 78 的基础上添加去重逻辑；最后横向比较两题的代码，感受"有重复"和"无重复"在代码层面的差异（就是一个 if 判断的区别）。

这个学习路径体现了算法学习的一个普遍规律：先理解简单情形（无重复），再处理复杂情形（有重复），通过对比加深理解。含重复元素的去重思想也会在组合总和 II（LeetCode 40）和全排列 II（LeetCode 47）中反复出现，掌握了 90 题的去重逻辑，这些题就迎刃而解了。

含重复元素子集的实际练习建议

要真正掌握含重复元素子集的去重，建议做以下练习：

手写 nums=[1,1,2] 的所有不重复子集（共6个：[],[1],[1,1],[2],[1,2],[1,1,2]）；然后跟踪回溯去重代码的执行，观察 i > start 和 nums[i]==nums[i-1] 条件在哪一步触发了去重；最后对比不加去重条件的执行结果（会多出 [1] 和 [1,2] 各一个重复），理解去重条件的效果。

这个追踪过程会让你对去重条件有直觉上的把握，不再需要靠死记硬背。面试时遇到含重复元素的组合/子集/排列问题，能立即想到"排序+同层去重"的模式并写出正确代码。

子集 II 的常见面试考点

含重复元素子集（LeetCode 90）在面试中常被用来考查以下几点：首先是能否在无重复子集（LeetCode 78）的代码基础上快速添加去重逻辑；其次是能否正确解释 i > start 条件的作用（很多候选人只写了 i > 0，无法正确解释为什么要用 i > start）；最后是能否举出具体例子验证去重条件的正确性（如 nums=[1,2,2]，说明 i=2 时如何被去重，以及 i=1 时为什么不被去重）。

能清晰回答这三点，就展示了对回溯去重的深刻理解，远超只会背代码的候选人。

含重复元素子集与排列的对比记忆

含重复元素子集（LeetCode 90）和含重复元素排列（LeetCode 47）都需要去重，但去重条件有一处关键差异：

子集/组合去重用 i > start（start 是当前层的起始下标），因为子集中元素按下标递增顺序选取，start 标记了当前层的范围起点。排列去重用 i > 0（不限制 start），因为排列中每层都是从整个未使用集合中选取，没有"起始下标"的概念，只需要判断前一个相同值是否在当前层被跳过（!visited[i-1]）。

一句话总结：子集用 i > start 是因为有位置约束（按下标顺序），排列用 i > 0 是因为无位置约束（任意顺序）。理解了这个差异，两种去重条件就不会再混淆。