题目
子集
思路
先确定需要的子数组的大小，（从 0 到 nums.size() 依次遍历），然后递归进行选择，每次递归都从上一个元素的下一位置开始，直到临时数组的大小等于当前确定的所需子数组的大小，将其加入结果数组。
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
vector<vector<int>> res;
vector<int> arr;
void dfs(vector<int> nums, int x, int npc){
if(x == arr.size()){
res.push_back(arr);
return;
}
for(int i = npc; i < nums.size(); i ++){
arr.push_back(nums[i]);
dfs(nums, x, i + 1);
arr.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
for(int i = 0; i <= nums.size(); i++){
dfs(nums, i, 0);
}
return res;
}
};
|
- 时间复杂度：O(n \ 2 ^ n)，一共 2 ^ n 个状态，每种状态需要 O(n) 的时间来构造子集。
- 空间复杂度：O(n)。临时数组 arr 的空间代价是 O(n)，递归时栈空间的代价为 O(n*)。
执行用时：4 ms, 在所有 C++ 提交中击败了43.18%的用户
内存消耗：7.6 MB, 在所有 C++ 提交中击败了13.53%的用户
通过测试用例：10 / 10
延伸题目
子集 II
思路
- 思路1：在上面的基础上，当满足条件时使用
map 进行去重，若重复则不加入，反之则加入。（需要先排序）
- 思路2：递归法实现子树枚举，在递归时，若发现没有选择上一个数，并且当前数字与上一个数字相同，则可以跳过当前生成的子集。
题解
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:
map<vector<int>, int> hsp;
vector<vector<int>> res;
vector<int> arr;
void dfs(vector<int> nums, int x, int npc){
if(arr.size() == x){
if(hsp[arr] == 1) return;
res.push_back(arr);
hsp[arr] = 1;
return ;
}
for(int i = npc; i < nums.size(); i++){
arr.push_back(nums[i]);
dfs(nums, x, i + 1);
arr.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
for(int i = 0; i <= nums.size(); i ++){
dfs(nums, i, 0);
}
return res;
}
};
|
- 时间复杂度：O(n \ 2 ^ n)，一共 2 ^ n 个状态，每种状态需要 O(n) 的时间来构造子集。
- 空间复杂度：O(n)。临时数组 arr 的空间代价是 O(n)，递归时栈空间的代价为 O(n*)。
执行用时：12 ms, 在所有 C++ 提交中击败了5.73%的用户
内存消耗：9.5 MB, 在所有 C++ 提交中击败了13.58%的用户
通过测试用例：20 / 20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
vector<vector<int>> res;
vector<int> arr;
void dfs(vector<int> nums, int x, bool pre){
if(x == nums.size()){
res.push_back(arr);
return ;
}
dfs(nums, x + 1, false);
if(!pre && x > 0 && nums[x] == nums[x - 1])
return;
arr.push_back(nums[x]);
dfs(nums, x + 1, true);
arr.pop_back();
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
dfs(nums, 0, false);
return res;
}
};
|
- 时间复杂度：O(n \ 2 ^ n)，其中 n 是数组 nums 的长度。排序的时间复杂度为 O(n * log n) 。最坏情况下 nums 中无重复元素，需要枚举其所有 2 ^ n 个子集，每个子集加入答案时需要拷贝一份，耗时 O(n) ，一共需要 O(n * 2 ^ n) + O(n) = O(n * 2 ^ n) 的时间来构造子集。由于在渐进意义上 O(n * log n) 小于O(n * 2 ^ n) ，故总的时间复杂度为 O(n * 2 ^ n)*
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 - 空间复杂度：O(n)。临时数组 arr 的空间代价是 O(n)，递归时栈空间的代价为 O(n*)。
执行用时：4 ms, 在所有 C++ 提交中击败了54.66%的用户
内存消耗：15.6 MB, 在所有 C++ 提交中击败了5.03%的用户
通过测试用例：20 / 20