【LetMeFly】90.子集 II：二进制枚举 / 回溯
力扣题目链接：https://leetcode.cn/problems/subsets-ii/
给你一个整数数组 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
解题方法一：位运算（二进制枚举）
使用变量$state$从$0$枚举到$2 ^ n - 1$，其中$state$二进制下的每一位代表选择$nums[i]$或不选。
枚举之前先将$nums$排序，若当前选择方案不存在则加入答案数组中。
- 时间复杂度$O(n\log n + n^2\times2^n)$，其中$n=len(nums)$
- 空间复杂度$O(n)$，返回值不计入
AC代码
C++
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
|
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
for (int i = 0; i < (1 << nums.size()); i++) {
vector<int> thisAns;
for (int j = 0; j < nums.size(); j++) {
if (i >> j & 1) {
thisAns.push_back(nums[j]);
}
}
if (find(ans.begin(), ans.end(), thisAns) == ans.end()) {
ans.push_back(thisAns);
}
}
return ans;
}
};
|
解题方法二：回溯
类似LeetCode 40.组合总和 II：回溯 + 剪枝，写一个dfs函数枚举选与不选两种情况。
- 如果当前下标已越界，则将当前方案添加到答案数组中
- 选当前元素时，将当前元素加入当前方案，递归，再将当前元素移除当前方案（回溯）
- 不选当前元素时，如果下一个元素（下下个元素，…）和当前元素一样，那么也不能选。
以上。
- 时间复杂度$O(n^\times2^n)$，其中$n=len(nums)$
- 空间复杂度$O(n)$，返回值不计入
AC代码
C++
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
30
31
32
33
34
|
class Solution {
private:
vector<vector<int>> ans;
vector<int> now;
void dfs(vector<int>& a, int loc) {
if (loc == a.size()) {
ans.push_back(now);
return;
}
now.push_back(a[loc]);
dfs(a, loc + 1);
now.pop_back();
int next = loc + 1;
while (next < a.size() && a[loc] == a[next]) {
next++;
}
dfs(a, next);
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
dfs(nums, 0);
return ans;
}
};
|
Python
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
| '''
Author: LetMeFly
Date: 2025-02-05 12:29:11
LastEditors: LetMeFly.xyz
LastEditTime: 2025-02-05 12:32:04
'''
from typing import List
class Solution:
def dfs(self, loc: int) -> None:
if loc == len(self.a):
self.ans.append([i for i in self.now])
return
self.now.append(self.a[loc])
self.dfs(loc + 1)
self.now.pop()
next = loc + 1
while next < len(self.a) and self.a[next] == self.a[loc]:
next += 1
self.dfs(next)
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
self.ans: List[List[int]] = []
self.a = sorted(nums)
self.now = []
self.dfs(0)
return self.ans
|
Java
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
30
31
32
33
34
35
36
37
38
39
|
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> now = new ArrayList<>();
private int[] a;
private void dfs(int loc) {
if (loc == a.length) {
ans.add(new ArrayList<>(now));
return;
}
now.add(a[loc]);
dfs(loc + 1);
now.remove(now.size() - 1);
int next = loc + 1;
while (next < a.length && a[next] == a[loc]) {
next++;
}
dfs(next);
}
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
a = nums;
dfs(0);
return ans;
}
}
|
Go
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
30
31
32
33
34
35
36
37
38
39
40
41
|
package main
import "sort"
var (
ans [][]int
now,
a []int
)
func dfs_S2(loc int) {
if loc == len(a) {
ans = append(ans, append([]int{}, now...))
return
}
now = append(now, a[loc])
dfs_S2(loc + 1)
now = now[:len(now) - 1]
next := loc + 1
for next < len(a) && a[next] == a[loc] {
next++
}
dfs_S2(next)
}
func subsetsWithDup(nums []int) [][]int {
ans = make([][]int, 0)
now = make([]int, 0)
sort.Ints(nums)
a = nums
dfs_S2(0)
return ans
}
|
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/145453136