子集 II
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你一个整数数组 nums，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1
[1,2] 与 [2,2] 各出现一次；不会出现两个相同的 [1,2]。示例 2
模拟答题者思考
1. 我先照搬 #78「子集」：每层把当前 path 记入答案，用 start 只往后选——在 [1,2,2] 上会得到 [1,2] 两次（两个 2 各走一条分支），违反「解集不能重复」。
2. 重复在哪里？一是排列等价（{1,2} 与 {2,1}），start 已解决；二是相同数值在同一层被多次当作「第一个新选元素」，生成相同子集（如两层都先选 2）。
3. 关键转化：先对 nums 排序；回溯框架与 #78 相同，但在 for i in range(start, n) 里加同层去重——若 i > start 且 nums[i] == nums[i-1] 则 continue（与 #40 组合总和 II 同款）。
4. 例 [1,2,2] 排序不变：收 [] → 选 1 收 [1] → 再选第一个 2 收 [1,2]、[1,2,2]；同层第二个 2 作为「本层起点」被跳过，但可在更深层被选中，故仍有 [2]、[2,2]。
5. n≤10，回溯足够；位运算枚举掩码也能做，但重复元素下掩码去重更绕，排序 + DFS 更直观。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
path | list<int> | 定义：当前正在构造的子集（按排序后下标递增选取的元素） 维护：DFS 在 path 末尾追加 nums[i]，回溯时 pop 撤销更新：进入一层递归前先记录当前 path；尝试分支时 append，返回后 pop |
start | int | 定义：本轮可选元素在排序后 nums 中的起始下标（含自身）维护：只从 start 往后选，保证子集内下标单调递增，避免排列等价重复更新：选了 nums[i] 后下一层传 start = i + 1 |
ans | list<list<int>> | 定义：幂集中全部互不相同的子集 维护：每次进入 DFS 时把当前 path 的副本加入（与 #78 子集相同，每层都是合法状态）更新：配合排序 + 同层去重，保证不会向 ans 写入重复子集 |
落码步骤
1. 对 nums 排序，初始化 ans 与 path
2. 定义 DFS backtrack(start)：先将 path[:] 加入 ans
3. 对 i 从 start 到 len(nums)-1：若 i > start 且 nums[i] == nums[i-1]，continue（同层去重）
4. 将 nums[i] 追加到 path，递归 backtrack(i + 1)
5. 回溯：从 path 弹出末尾，继续尝试更大的 i
6. 从 backtrack(0) 启动，返回 ans
代码实现
class Solution:
def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
nums.sort()
ans: list[list[int]] = []
path: list[int] = []
def backtrack(start: int) -> None:
ans.append(path[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue
path.append(nums[i])
backtrack(i + 1)
path.pop()
backtrack(0)
return ansclass Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
vector<int> path;
function<void(int)> dfs = [&](int start) {
ans.push_back(path);
for (int i = start; i < (int)nums.size(); i++) {
if (i > start && nums[i] == nums[i - 1]) continue;
path.push_back(nums[i]);
dfs(i + 1);
path.pop_back();
}
};
dfs(0);
return ans;
}
};
// 时间 O(n·2^n)，空间 O(n) 递归栈复杂度分析
O(n · 2^n)（最坏仍枚举全部不同子集；排序与同层去重减少重复输出）
O(n)（递归栈深度与当前路径，不计输出）
常见坑
未排序就同层去重：nums[i]==nums[i-1] 只在相邻相等时有效，必须先 sort，否则重复值分散在不同位置无法跳过。
去重条件写成 i > 0：会误杀「不同层各选一个相同值」的合法子集（如 [1,1]）；必须是 i > start，只跳过同一层的重复起点。
只在叶子收集：与 #78 相同，应在每层 DFS 入口记录 path，否则漏掉「不再往下选」的中间子集（如只含一个 2 的 [2]）。
必测边界 Case
nums = [2,2,2] → [[],[2],[2,2],[2,2,2]] 共 4 项
nums = [1,2,2] → 6 个子集，无重复
nums = [0] → [[],[0]]
任意 nums → ans 第一项为 []
nums = [-1,0,1] → 排序后回溯，子集个数仍为 2^n