题目描述
给定一个集合，包含互不相同的数，返回它的所有子集（幂集）。
注意；结果不能包含相同子集。
样例
输入：nums = [1,2,3]
输出：
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
算法
(集合的二进制表示) $O(2^nn)$
假设集合大小是 $n$，我们枚举 $0 … 2^n-1$，一共 $2^n$ 个数。
每个数表示一个子集，假设这个数的二进制表示的第 $i$ 位是1，则表示该子集包含第 $i$ 个数，否则表示不包含。
另外，如果 $n \ge 30$，则 $2^n \ge 10^9$，肯定会超时，所以我们可以断定 $n \le 30$，可以用int型变量来枚举。
时间复杂度分析：一共枚举 $2^n$ 个数，每个数枚举 $n$ 位，所以总时间复杂度是 $O(2^nn)$。
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;
}
};
y总在视频里提了一下但是没有写的递归写法
为什么两次dfs
一次是选这个点，一次是不选这个点
我觉得不需要两次dfs
这样做好像最多只能hold nums的size 也就是n最多为32的情况 但题目其实没说这个限制 所以题解可能得改成用bitset？
这里如果 $n = 30$，$2^{30} \approx 10^9$，肯定会超时了，所以可以判断出 $n \le 30$ ，这里我应该在题解里提一下的hh。