题目描述
幂集。编写一种方法,返回某集合的所有子集。集合中不包含重复的元素。
说明:解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
解法
方法一:递归枚举
我们设计一个递归函数 $dfs(u, t)$,它的参数为当前枚举到的元素的下标 $u$,以及当前的子集 $t$。
当前枚举到的元素下标为 $u$,我们可以选择将其加入子集 $t$ 中,也可以选择不加入子集 $t$ 中。递归这两种选择,即可得到所有的子集。
时间复杂度 $O(n \times 2^n)$,空间复杂度 $O(n)$。其中 $n$ 为数组的长度。数组中每个元素有两种状态,即选择或不选择,共 $2^n$ 种状态,每种状态需要 $O(n)$ 的时间来构造子集。
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
def dfs(u, t):
if u == len(nums):
ans.append(t[:])
return
dfs(u + 1, t)
t.append(nums[u])
dfs(u + 1, t)
t.pop()
ans = []
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 | class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private int[] nums;
public List<List<Integer>> subsets(int[] nums) {
this.nums = nums;
dfs(0, new ArrayList<>());
return ans;
}
private void dfs(int u, List<Integer> t) {
if (u == nums.length) {
ans.add(new ArrayList<>(t));
return;
}
dfs(u + 1, t);
t.add(nums[u]);
dfs(u + 1, t);
t.remove(t.size() - 1);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> t;
dfs(0, nums, t, ans);
return ans;
}
void dfs(int u, vector<int>& nums, vector<int>& t, vector<vector<int>>& ans) {
if (u == nums.size()) {
ans.push_back(t);
return;
}
dfs(u + 1, nums, t, ans);
t.push_back(nums[u]);
dfs(u + 1, nums, t, ans);
t.pop_back();
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | func subsets(nums []int) [][]int {
var ans [][]int
var dfs func(u int, t []int)
dfs = func(u int, t []int) {
if u == len(nums) {
ans = append(ans, append([]int(nil), t...))
return
}
dfs(u+1, t)
t = append(t, nums[u])
dfs(u+1, t)
t = t[:len(t)-1]
}
var t []int
dfs(0, t)
return ans
}
|
| function subsets(nums: number[]): number[][] {
const res = [[]];
nums.forEach(num => {
res.forEach(item => {
res.push(item.concat(num));
});
});
return res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12 | impl Solution {
pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
let n = nums.len();
let mut res: Vec<Vec<i32>> = vec![vec![]];
for i in 0..n {
for j in 0..res.len() {
res.push(vec![..res[j].clone(), vec![nums[i]]].concat());
}
}
res
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | /**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function (nums) {
let prev = [];
let res = [];
dfs(nums, 0, prev, res);
return res;
};
function dfs(nums, depth, prev, res) {
res.push(prev.slice());
for (let i = depth; i < nums.length; i++) {
prev.push(nums[i]);
depth++;
dfs(nums, depth, prev, res);
prev.pop();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution {
private var ans = [[Int]]()
private var nums: [Int] = []
func subsets(_ nums: [Int]) -> [[Int]] {
self.nums = nums
dfs(0, [])
return ans.sorted { $0.count < $1.count }
}
private func dfs(_ u: Int, _ t: [Int]) {
if u == nums.count {
ans.append(t)
return
}
dfs(u + 1, t)
var tWithCurrent = t
tWithCurrent.append(nums[u])
dfs(u + 1, tWithCurrent)
}
}
|
方法二:二进制枚举
我们可以将方法一中的递归过程改写成迭代的形式,即使用二进制枚举的方法来枚举所有的子集。
我们可以使用 $2^n$ 个二进制数来表示 $n$ 个元素的所有子集,若某个二进制数 mask
的第 $i$ 位为 $1$,表示子集中包含数组第 $i$ 个元素 $v$;若为 $0$,表示子集中不包含数组第 $i$ 个元素 $v$。
时间复杂度 $O(n \times 2^n)$,空间复杂度 $O(n)$。其中 $n$ 为数组的长度。一共有 $2^n$ 个子集,每个子集需要 $O(n)$ 的时间来构造。
| class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
ans = []
for mask in range(1 << len(nums)):
t = []
for i, v in enumerate(nums):
if (mask >> i) & 1:
t.append(v)
ans.append(t)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution {
public List<List<Integer>> subsets(int[] nums) {
int n = nums.length;
List<List<Integer>> ans = new ArrayList<>();
for (int mask = 0; mask < 1 << n; ++mask) {
List<Integer> t = new ArrayList<>();
for (int i = 0; i < n; ++i) {
if (((mask >> i) & 1) == 1) {
t.add(nums[i]);
}
}
ans.add(t);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> t;
int n = nums.size();
for (int mask = 0; mask < 1 << n; ++mask) {
t.clear();
for (int i = 0; i < n; ++i) {
if ((mask >> i) & 1) {
t.push_back(nums[i]);
}
}
ans.push_back(t);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | func subsets(nums []int) [][]int {
var ans [][]int
n := len(nums)
for mask := 0; mask < 1<<n; mask++ {
t := []int{}
for i, v := range nums {
if ((mask >> i) & 1) == 1 {
t = append(t, v)
}
}
ans = append(ans, t)
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | function subsets(nums: number[]): number[][] {
const n = nums.length;
const res = [];
const list = [];
const dfs = (i: number) => {
if (i === n) {
res.push([...list]);
return;
}
list.push(nums[i]);
dfs(i + 1);
list.pop();
dfs(i + 1);
};
dfs(0);
return res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | impl Solution {
fn dfs(nums: &Vec<i32>, i: usize, res: &mut Vec<Vec<i32>>, list: &mut Vec<i32>) {
if i == nums.len() {
res.push(list.clone());
return;
}
list.push(nums[i]);
Self::dfs(nums, i + 1, res, list);
list.pop();
Self::dfs(nums, i + 1, res, list);
}
pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut res = vec![];
Self::dfs(&nums, 0, &mut res, &mut vec![]);
res
}
}
|