题目链接
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
1
2
| 输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
|
示例 2：
1
2
| 输入：nums = [0]
输出：[[],[0]]
|
nums 中的所有元素互不相同
二进制枚举子集
n 为元素的集合，子集的个数(含空集)为2n，表示 2n 种状态。假设集合为nums = [1,2,3]，它的子集表示如下：
| 子集 |
二进制 |
对应十进制 |
| [] |
000 |
0 |
| [1] |
001 |
1 |
| [2] |
010 |
2 |
| [1,2] |
011 |
3 |
| [3] |
100 |
4 |
| [1,3] |
101 |
5 |
| [2,3] |
110 |
6 |
| [1,2,3] |
111 |
7 |
从 000 到 111 总共包含 23 种状态，恰好对应子集的个数。我们将对应的二进制位为 1 表示取集合中该位置元素，为 0 表示不取集合中该位置元素。例如010，二进制位的序号为 0，1，2，下标 0 和 2为 0 ，不取，下标 1 为 1，表示取，所以该子集为 [nums[1]] = [2]。
代码如下：
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> tem;
int len = nums.size();
for (int mask = 0; mask < (1 << len); ++mask) {
tem.clear();
for (int i = 0; i < len; ++i) {
if (mask & (1 << i)) {
tem.push_back(nums[i]);
}
}
ans.push_back(tem);
}
return ans;
}
};
|
用 1 << len 得到 2n
时间复杂度
n 个元素的集合，总共有 2n种状态，每种状态都需要遍历 n 次，总的时间复杂度为 O(n 2n)
空间复杂度
临时数组 tem 的空间，空间复杂度为 O(n)
回溯
对于 n 个元素的集合来说，我们需要对集合做 n 次选择，从左到右选择元素，对于每一个元素，要么选，要么不选，所以可以用回溯法来实现。
递归树如下：
代码如下：
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>> ans;
vector<int> tem;
void dfs(int cur,vector<int>& nums){
if(cur==nums.size()){
ans.push_back(tem);
return;
}
tem.push_back(nums[cur]);
dfs(cur+1,nums);
tem.pop_back();
dfs(cur+1,nums);
}
vector<vector<int>> subsets(vector<int>& nums) {
dfs(0,nums);
return ans;
}
};
|
时间复杂度
根据递归树可知，它的叶子节点个数为子集个数，叶节点个数为 2n ，构建每个子集都需要 O(n) 的时间，所以总的时间为 O(n 2n)。
空间复杂度
临时数组 tem O(n) ，递归的深度为 n，每次递归空间复杂度为 O(1)。所以总的空间复杂度为: O(n)。
进阶——存在重复元素
题目链接
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
1
2
| 输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
|
示例 2：
1
2
| 输入：nums = [0]
输出：[[],[0]]
|
二进制枚举
给定一个集合[1,2,2]，当选择元素 x ，若前面有一个相同元素 y 并没有被选取，那么包含 x 的所有子集必然会出现包含 y 的子集中。我们可以通过判断，排除存在重复的子集。
在开始枚举之前，现将 nums 数组进行排序。
代码如下：
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
| class Solution {
public:
vector<vector<int>> ans;
vector<int> tem;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
int len = nums.size();
bool isuse;
sort(nums.begin(),nums.end());
for(int mask=0; mask< (1<<len); ++mask){
tem.clear();
isuse = true;
for(int i = 0; i<len; ++i){
if(1&(mask>>i)){
if(i>0 && nums[i]==nums[i-1] && !(1&(mask>>(i-1)))){
isuse = false;
break;
}else{
tem.push_back(nums[i]);
}
}
}
if(isuse)
ans.push_back(tem);
}
return ans;
}
};
|
时间复杂度：
排序时间复杂度为 O(n lgn)，总共构造 2n 个子集，构造每个子集所需时间为 O(n)，生成所有子集的时间为 O(n 2n)，因为从渐进意义上来讲 O(n lgn) < O(n 2n)，所以总的时间复杂度为 O(n 2n)
空间复杂度
使用了一个长度最多为 n 的临时数组，所以为 O(n)
回溯
不存在重复元素的情况类似，当选择元素 x ，若前面有一个相同元素 y 并没有被选取，那么包含 x 的所有子集必然会出现包含 y 的子集中。若当前元素为符合上述条件中的 x，则直接返回。
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
| class Solution {
public:
vector<vector<int>> ans;
vector<int> tem;
void dfs(int cur, vector<int>& nums,bool pre){
if(cur==nums.size()){
ans.push_back(tem);
return;
}
dfs(cur+1,nums,false);
if(!pre && cur>0 && nums[cur]==nums[cur-1]){
return;
}
tem.push_back(nums[cur]);
dfs(cur+1,nums,true);
tem.pop_back();
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(),nums.end());
dfs(0,nums,false);
return ans;
}
};
|
时间复杂度：
最坏情况下为不存在重复元素，排序所需时间 O(n lgn)，1 个叶节点代表一个子集，叶节点的个数为 2n，构造每个子集需要 O(n)，构造子集的时间为 O(n 2n)，O(n lgn) < O(n 2n),时间复杂度总是忽略低阶项，所以全过程的时间复杂度为 O(n 2n)
空间复杂度
使用一个临时数组 tem，递归最深时栈空间 O(n)，总的空间复杂度为 O(n)