题目描述
给你一个整数数组 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
我们可以先对数组 \(\textit{nums}\) 进行排序，方便去重。
然后，我们设计一个函数 \(\textit{dfs}(i)\)，表示当前从第 \(i\) 个元素开始搜索子集。函数 \(\textit{dfs}(i)\) 的执行逻辑如下：
如果 \(i \geq n\)，说明已经搜索完所有元素，将当前子集加入答案数组中，递归结束。
如果 \(i < n\)，将第 \(i\) 个元素加入子集，执行 \(\textit{dfs}(i + 1)\)，然后将第 \(i\) 个元素从子集中移除。接下来，我们判断第 \(i\) 个元素是否和下一个元素相同，如果相同，则循环跳过该元素，直到找到第一个和第 \(i\) 个元素不同的元素，执行 \(\textit{dfs}(i + 1)\)。
最后，我们只需要调用 \(\textit{dfs}(0)\)，返回答案数组即可。
时间复杂度 \(O(n \times 2^n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是数组 \(\textit{nums}\) 的长度。
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) {
ranges::sort(nums);
vector<vector<int>> ans;
vector<int> t;
int n = nums.size();
auto dfs = [&](this auto&& 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) {
slices.Sort(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
}
}
|
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 | /**
* @param {number[]} nums
* @return {number[][]}
*/
var subsetsWithDup = function (nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
const t = [];
const ans = [];
const dfs = i => {
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 | public class Solution {
private IList<IList<int>> ans = new List<IList<int>>();
private IList<int> t = new List<int>();
private int[] nums;
public IList<IList<int>> SubsetsWithDup(int[] nums) {
Array.Sort(nums);
this.nums = nums;
Dfs(0);
return ans;
}
private void Dfs(int i) {
if (i >= nums.Length) {
ans.Add(new List<int>(t));
return;
}
t.Add(nums[i]);
Dfs(i + 1);
t.RemoveAt(t.Count - 1);
while (i + 1 < nums.Length && nums[i + 1] == nums[i]) {
++i;
}
Dfs(i + 1);
}
}
|
方法二：排序 + 二进制枚举
与方法一类似，我们先对数组 \(\textit{nums}\) 进行排序，方便去重。
接下来，我们在 \([0, 2^n)\) 的范围内枚举一个二进制数 \(\textit{mask}\)，其中 \(\textit{mask}\) 的二进制表示是一个 \(n\) 位的位串，如果 \(\textit{mask}\) 的第 \(i\) 位为 \(1\)，表示选择 \(\textit{nums}[i]\)，为 \(0\) 表示不选择 \(\textit{nums}[i]\)。注意，如果 \(\textit{mask}\) 的 \(i - 1\) 位为 \(0\)，且 \(\textit{nums}[i] = \textit{nums}[i - 1]\)，则说明在当前枚举到的方案中，第 \(i\) 个元素和第 \(i - 1\) 个元素相同，为了避免重复，我们跳过这种情况。否则，我们将 \(\textit{mask}\) 对应的子集加入答案数组中。
枚举结束后，我们返回答案数组即可。
时间复杂度 \(O(n \times 2^n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是数组 \(\textit{nums}\) 的长度。