90. Subsets II

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

1
2
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Example 2:

1
2
Input: nums = [0]
Output: [[],[0]]

题目大意

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（即幂集）。幂集需包含所有可能的子集（包括空集和数组本身），且不能有重复子集，结果顺序可任意。

例如：

  • 输入 nums = [1,2,2]，输出 [[],[1],[1,2],[1,2,2],[2],[2,2]]（共 6 个子集，无重复）；
  • 输入 nums = [0]，输出 [[],[0]]（共 2 个子集）。

解题思路

核心思路是递归回溯 + 排序去重，在允许数组包含重复元素的情况下，通过控制选择逻辑避免生成重复子集：

1. 排序预处理：为去重奠基

首先对 nums 排序（如 [2,1,2] 排序为 [1,2,2]），使相同元素相邻。这是去重的关键 —— 只有相同元素集中排列，才能通过 “跳过同层重复元素” 避免生成重复子集。

2. 递归状态定义

递归函数 dfs(i) 表示：从数组索引 i 开始选择元素，构建当前子集 path。

  • i：当前选择的起始索引（确保元素按 “从左到右” 顺序选择，避免 [1,2] 和 [2,1] 这类重复）；
  • path：临时存储当前正在构建的子集；
  • ans：收集所有无重复子集（每进入一次递归就收集当前 path，包括空集）。

3. 核心决策逻辑：“选当前元素” 与 “同层去重”

在递归函数中，遍历从 i 到 n-1 的所有元素，对每个元素 nums[j] 做两件事：

同层去重：跳过重复元素

若 j > i（说明当前元素不是当前层的第一个元素），且 nums[j] == nums[j-1]（当前元素与前一个元素相同），则直接跳过。
原理：当前层中，前一个相同元素 nums[j-1] 已被考虑过 “选或不选”，若再选 nums[j]，会生成与 nums[j-1] 对应的子集重复的结果。
例如：排序后的 [1,2,2]，当 i=1 时（处理第二个元素）：

  • j=1 选 2，生成 [2]；
  • j=2 时，因 j>1 且 nums[2]==nums[1]，跳过，避免生成重复的 [2]。

选择当前元素：递归 + 回溯

若元素不重复，则：

  • 将 nums[j] 加入 path（选择当前元素）；
  • 递归调用 dfs(j+1)（下一次从 j+1 开始选择，确保每个元素仅被选一次）；
  • 回溯：path.pop_back()（移除当前元素，恢复状态，尝试选择下一个元素）。

4. 子集收集时机

每进入一次 dfs 就收集当前 path—— 因为子集不限制长度，从空集（初始 path 为空）到完整数组，所有中间状态都是有效子集。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        ranges::sort(nums);
        int n = nums.size();
        vector<vector<int>> ans;
        vector<int> path;

        auto dfs = [&](this auto&& dfs, int i) -> void {
            ans.push_back(path);

            // 在 [i,n-1] 中选一个 nums[j]
            // 注意选 nums[j] 意味着 [i,j-1] 中的数都没有选
            for (int j = i; j < n; j++) {
                // 如果 j>i，说明 nums[j-1] 没有选
                // 同方法一，所有等于 nums[j-1] 的数都不选
                if (j > i && nums[j] == nums[j - 1]) {
                    continue;
                }
                path.push_back(nums[j]);
                dfs(j + 1);
                path.pop_back(); // 恢复现场
            }
        };

        dfs(0);
        return ans;
    }
};