题目描述
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10
解法
方法一：排序 + DFS
我们可以先对数组 $nums$ 进行排序，方便去重。
然后，我们设计一个函数 $dfs(i)$，表示当前从第 $i$ 个元素开始搜索子集。函数 $dfs(i)$ 的执行逻辑如下：
如果 $i \geq n$，说明已经搜索完所有元素，将当前子集加入答案数组中，递归结束。
如果 $i < n$，将第 $i$ 个元素加入子集，执行 $dfs(i + 1)$，然后将第 $i$ 个元素从子集中移除。接下来，我们判断第 $i$ 个元素是否和下一个元素相同，如果相同，则循环跳过该元素，直到找到第一个和第 $i$ 个元素不同的元素，执行 $dfs(i + 1)$。
最后，我们只需要调用 $dfs(0)$，返回答案数组即可。
时间复杂度 $O(n \times 2^n)$，空间复杂度 $O(n)$。其中 $n$ 是数组的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
def dfs(i: int):
if i == len(nums):
ans.append(t[:])
return
t.append(nums[i])
dfs(i + 1)
x = t.pop()
while i + 1 < len(nums) and nums[i + 1] == x:
i += 1
dfs(i + 1)
nums.sort()
ans = []
t = []
dfs(0)
return ans
|
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 | class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> t = new ArrayList<>();
private int[] nums;
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
this.nums = nums;
dfs(0);
return ans;
}
private void dfs(int i) {
if (i >= nums.length) {
ans.add(new ArrayList<>(t));
return;
}
t.add(nums[i]);
dfs(i + 1);
int x = t.remove(t.size() - 1);
while (i + 1 < nums.length && nums[i + 1] == x) {
++i;
}
dfs(i + 1);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
vector<int> t;
int n = nums.size();
function<void(int)> dfs = [&](int i) {
if (i >= n) {
ans.push_back(t);
return;
}
t.push_back(nums[i]);
dfs(i + 1);
t.pop_back();
while (i + 1 < n && nums[i + 1] == nums[i]) {
++i;
}
dfs(i + 1);
};
dfs(0);
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | func subsetsWithDup(nums []int) (ans [][]int) {
sort.Ints(nums)
n := len(nums)
t := []int{}
var dfs func(int)
dfs = func(i int) {
if i >= n {
ans = append(ans, slices.Clone(t))
return
}
t = append(t, nums[i])
dfs(i + 1)
t = t[:len(t)-1]
for i+1 < n && nums[i+1] == nums[i] {
i++
}
dfs(i + 1)
}
dfs(0)
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | function subsetsWithDup(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const n = nums.length;
const t: number[] = [];
const ans: number[][] = [];
const dfs = (i: number): void => {
if (i >= n) {
ans.push([...t]);
return;
}
t.push(nums[i]);
dfs(i + 1);
t.pop();
while (i + 1 < n && nums[i] === nums[i + 1]) {
i++;
}
dfs(i + 1);
};
dfs(0);
return ans;
}
|
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 | impl Solution {
pub fn subsets_with_dup(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut nums = nums;
nums.sort();
let mut ans = Vec::new();
let mut t = Vec::new();
fn dfs(i: usize, nums: &Vec<i32>, t: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
if i >= nums.len() {
ans.push(t.clone());
return;
}
t.push(nums[i]);
dfs(i + 1, nums, t, ans);
t.pop();
let mut i = i;
while i + 1 < nums.len() && nums[i + 1] == nums[i] {
i += 1;
}
dfs(i + 1, nums, t, ans);
}
dfs(0, &nums, &mut t, &mut ans);
ans
}
}
|
方法二：排序 + 二进制枚举
与方法一类似，我们先对数组 $nums$ 进行排序，方便去重。
接下来，我们在 $[0, 2^n)$ 的范围内枚举一个二进制数 $mask$，其中 $mask$ 的二进制表示是一个 $n$ 位的位串，如果 $mask$ 的第 $i$ 位为 $1$，表示选择 $nums[i]$，为 $0$ 表示不选择 $nums[i]$。注意，如果 $mask$ 的 $i - 1$ 位为 $0$，且 $nums[i] = nums[i - 1]$，则说明在当前枚举到的方案中，第 $i$ 个元素和第 $i - 1$ 个元素相同，为了避免重复，我们跳过这种情况。否则，我们将 $mask$ 对应的子集加入答案数组中。
枚举结束后，我们返回答案数组即可。
时间复杂度 $O(n \times 2^n)$，空间复杂度 $O(n)$。其中 $n$ 是数组的长度。