解法一:递归
1、思路
-
遍历数组,对于每个元素有选和不选两种情况,将每种情况都放到结果数组中即可;
-
时间复杂度为 $O(N) ,空间复杂度为 $O(N) 。
2、代码
class Solution {
public:
void dfs(vector<int>& nums, vector<vector<int>>& res, vector<int>& tmp, int i)
{
if (i == nums.size()) return;
tmp.push_back(nums[i]);
res.push_back(tmp);
dfs(nums, res, tmp, i + 1); //选择当前元素
tmp.pop_back();
dfs(nums, res, tmp, i + 1); //不选当前元素
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
vector<int> tmp;
res.push_back(tmp); //先放入一个空集
dfs(nums, res, tmp, 0);
return res;
}
};
解法二:迭代
1、思路
-
因为每个元素有选和不选两种情况,所以长度为 $n$ 的数组,其子集个数有 $2^n$ 个;
-
构造所有子集就等同于构造所有的二进制数,迭代访问从 $1$ 到 $2^n$ 的所有数字,再将这些数字的二进制表示转换成集合即可;
-
时间复杂度为 $O(N) ,空间复杂度为 $O(N) 。
2、代码
class Solution {
public:
vector<int> convertIntToVector(vector<int>& nums, int i)
{
vector<int> subset;
int idx = 0;
// 遍历数字 i 的二进制位,若为 1 表示选择当前元素
for (int j = i; j > 0; j >>= 1)
{
if ((j & 1) == 1)
{
subset.push_back(nums[idx]);
}
++ idx;
}
return subset;
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
int max = 1 << nums.size(); //一共有 2^n 个子集
for (int i = 0; i < max; ++ i)
{
res.push_back(convertIntToVector(nums, i));
}
return res;
}
};