90. 子集 II
题目描述
输入整数数组 nums，其中可能有重复元素。
返回 nums 的所有子集（幂集）。由同样的一组数组成的子集只算一个，结果里不能重复。
子集之间的顺序不限。
示例 1
输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
解释：两个 2 是重复元素，[1,2] 和 [2] 各只算一次，共 6 个子集。
示例 2
输入：nums = [0] 输出：[[],[0]]
数据范围
1 <= nums.length <= 10-10 <= nums[i] <= 10
解题思路：排序 + 回溯去重
排序后用 dfs(start) 枚举子集：每进入一层先记录当前 path，再从 start 开始挑下一个元素。去重规则：同一层中，如果 nums[i] 与 nums[i-1] 相同且 i > start，就跳过——因为用 nums[i-1] 开头的分支已经覆盖了用 nums[i] 开头的所有情况。
为什么正确
同一层中每个数值最多被选为“下一个元素”一次，且选的是它在 [start, n) 中的第一次出现。
复杂度分析
时间 O(n · 2^n)，空间 O(n)（不计输出）。
易错点
写成 i > 0 而不是 i > start 会把 [2,2] 这种纵向使用重复值的子集也剪掉；忘记排序则重复值不相邻，去重失效。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res, path = [], []
def dfs(start):
res.append(path[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue
path.append(nums[i])
dfs(i + 1)
path.pop()
dfs(0)
return resclass Solution {
int[] nums;
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
this.nums = nums;
dfs(0);
return res;
}
void dfs(int start) {
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]);
dfs(i + 1);
path.remove(path.size() - 1);
}
}
}class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
vector<int> path;
function<void(int)> dfs = [&](int start) {
res.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 res;
}
};func subsetsWithDup(nums []int) [][]int {
sort.Ints(nums)
res, path := [][]int{}, []int{}
var dfs func(start int)
dfs = func(start int) {
res = append(res, append([]int{}, path...))
for i := start; i < len(nums); i++ {
if i > start && nums[i] == nums[i-1] {
continue
}
path = append(path, nums[i])
dfs(i + 1)
path = path[:len(path)-1]
}
}
dfs(0)
return res
}var subsetsWithDup = function(nums) {
nums.sort((a, b) => a - b);
const res = [], path = [];
const dfs = (start) => {
res.push([...path]);
for (let i = start; i < nums.length; i++) {
if (i > start && nums[i] === nums[i - 1]) {
continue;
}
path.push(nums[i]);
dfs(i + 1);
path.pop();
}
};
dfs(0);
return res;
};function subsetsWithDup(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const res: number[][] = [], path: number[] = [];
const dfs = (start: number): void => {
res.push([...path]);
for (let i = start; i < nums.length; i++) {
if (i > start && nums[i] === nums[i - 1]) {
continue;
}
path.push(nums[i]);
dfs(i + 1);
path.pop();
}
};
dfs(0);
return res;
}其他解法
二进制枚举先枚举全部掩码再过滤重复；回溯在同一层跳过相同元素，直接不生成重复子集，重复越多优势越大。两者的去重条件本质相同：相同元素只能按顺序使用。
解法 2：二进制枚举 + 去重规则 时间 O(n·2ⁿ)，空间 O(n)
先排序，让相同元素挨在一起。然后像第 78 题一样枚举 0 到 2ⁿ-1 的每个掩码。为了去重，规定一组相同元素只能“从前往后连续地选”：如果选了 nums[i]，而 nums[i-1] 与它相等却没被选，这个掩码就和另一个掩码对应同一个子集，直接跳过。
不需要递归，去重规则只是一个局部判断。但它仍会枚举全部 2ⁿ 个掩码，重复元素很多时会做大量无用工作；回溯则在搜索时就把重复分支剪掉了。
from typing import List
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
res = []
for mask in range(1 << n):
cur = []
ok = True
for i in range(n):
if mask >> i & 1:
# 相同元素只允许“从前往后连续选”，否则会产生重复子集
if i > 0 and not (mask >> (i - 1) & 1) and nums[i] == nums[i - 1]:
ok = False
break
cur.append(nums[i])
if ok:
res.append(cur)
return resclass Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
List<List<Integer>> res = new ArrayList<>();
for (int mask = 0; mask < (1 << n); mask++) {
List<Integer> cur = new ArrayList<>();
boolean ok = true;
for (int i = 0; i < n; i++) {
if ((mask >> i & 1) == 1) {
if (i > 0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i - 1]) {
ok = false;
break;
}
cur.add(nums[i]);
}
}
if (ok) res.add(cur);
}
return res;
}
}class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
vector<vector<int>> res;
for (int mask = 0; mask < (1 << n); mask++) {
vector<int> cur;
bool ok = true;
for (int i = 0; i < n; i++) {
if (mask >> i & 1) {
if (i > 0 && !(mask >> (i - 1) & 1) && nums[i] == nums[i - 1]) {
ok = false;
break;
}
cur.push_back(nums[i]);
}
}
if (ok) res.push_back(cur);
}
return res;
}
};import "sort"
func subsetsWithDup(nums []int) [][]int {
sort.Ints(nums)
n := len(nums)
res := [][]int{}
for mask := 0; mask < 1<<n; mask++ {
cur := []int{}
ok := true
for i := 0; i < n; i++ {
if mask>>i&1 == 1 {
if i > 0 && mask>>(i-1)&1 == 0 && nums[i] == nums[i-1] {
ok = false
break
}
cur = append(cur, nums[i])
}
}
if ok {
res = append(res, cur)
}
}
return res
}var subsetsWithDup = function(nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
const res = [];
for (let mask = 0; mask < (1 << n); mask++) {
const cur = [];
let ok = true;
for (let i = 0; i < n; i++) {
if (mask >> i & 1) {
if (i > 0 && !(mask >> (i - 1) & 1) && nums[i] === nums[i - 1]) {
ok = false;
break;
}
cur.push(nums[i]);
}
}
if (ok) res.push(cur);
}
return res;
};function subsetsWithDup(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const n = nums.length;
const res: number[][] = [];
for (let mask = 0; mask < (1 << n); mask++) {
const cur: number[] = [];
let ok = true;
for (let i = 0; i < n; i++) {
if (mask >> i & 1) {
if (i > 0 && !(mask >> (i - 1) & 1) && nums[i] === nums[i - 1]) {
ok = false;
break;
}
cur.push(nums[i]);
}
}
if (ok) res.push(cur);
}
return res;
}