题目描述
给定一个集合,包含互不相同的数,返回它的所有子集(幂集)。
注意;结果不能包含相同子集。
样例
输入:nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
算法
(集合的二进制表示) O(2nn)
假设集合大小是 n,我们枚举 0…2n−1,一共 2n 个数。
每个数表示一个子集,假设这个数的二进制表示的第 i 位是1,则表示该子集包含第 i 个数,否则表示不包含。
另外,如果 n≥30,则 2n≥109,肯定会超时,所以我们可以断定 n≤30,可以用int
型变量来枚举。
时间复杂度分析:一共枚举 2n 个数,每个数枚举 n 位,所以总时间复杂度是 O(2nn)。
C++ 代码
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
int n = nums.size();
for (int i = 0; i < (1 << n); i ++ )
{
vector<int> temp;
for (int j = 0; j < n; j ++ )
if (i >> j & 1)
temp.push_back(nums[j]);
res.push_back(temp);
}
return res;
}
};
class Solution { public: int n; vector<vector<int>> res; vector<int> path; vector<vector<int>> subsets(vector<int>& nums) { //采用递归的写法,如果每次看是否选择当前数,如果选择则为一种方案,不选为另外一种方案 n = nums.size(); dfs(nums, path, 0); return res; } void dfs(vector<int>& nums,vector<int>& path,int u){ if(u == n){ res.push_back(path); return; } path.push_back(nums[u]); dfs(nums, path, u + 1); path.pop_back(); dfs(nums, path, u + 1); } };
y总在视频里提了一下但是没有写的递归写法
为什么两次dfs
一次是选这个点,一次是不选这个点
我觉得不需要两次dfs
class Solution { public: vector<bool> flag; vector<vector<int>> ans; vector<vector<int>> subsets(vector<int>& nums) { int n = nums.size(); flag = vector<bool>(n, false); vector<int> v; dfs(nums, 0, v); return ans; } void dfs(vector<int>& nums, int u, vector<int>& v){ if(v.size() <= nums.size()){ ans.push_back(v); } for(int i = u; i < nums.size(); i++){ if(flag[i] == false){ flag[i] = true; v.push_back(nums[i]); dfs(nums, i + 1, v); v.pop_back(); flag[i] = false; } } } };
class Solution { public: vector<vector<int>> res; vector<int> path; vector<vector<int>> subsets(vector<int>& nums) { dfs(nums, 0); return res; } void dfs(vector<int>& nums, int u) { res.push_back(path); // 收集子集,要放在终止条件的上面,否则会漏掉自己 if (nums.size() == u) return; // 终止条件可以不加 for (int i = u; i < nums.size(); i++) { path.push_back(nums[i]); dfs(nums, i + 1); path.pop_back(); } } };
这样做好像最多只能hold nums的size 也就是n最多为32的情况 但题目其实没说这个限制 所以题解可能得改成用bitset?
这里如果 n=30,230≈109,肯定会超时了,所以可以判断出 n≤30 ,这里我应该在题解里提一下的hh。