78 子集
迭代法
用二进制表示每个幂集,第i位为1表示选择第i个元素,那么总共有2^n - 1个状态
class Solution {
private:
vector<int> t;
vector<vector<int>> ans;
public:
vector<vector<int>> subsets(vector<int>& nums) {
int n = nums.size();
// 总共有2^n - 1种状态
for(int mask = 0; mask < (1 << n); mask++){
// 每个状态对应的序列不同
t.clear();
// 枚举每个元素
for(int i = 0; i < n; i++){
// 1 << i表示第i位为1
// mask & (1 << i)表示mask状态第i位为1
// 即选择第i个元素
if(mask & (1 << i)){
t.push_back(nums[i]);
}
}
ans.push_back(t);
}
return ans;
}
};
递归法
用idx记录当前遍历到第几个元素,分类讨论:
- 选择当前元素,如果选择当前元素,那么dfs之后需要回溯
- 不选择当前元素
class Solution {
private:
vector<vector<int>> ans;
vector<int> res;
void dfs(vector<int>&nums, int idx){
if(idx == nums.size()){
ans.push_back(res);
return;
}
res.push_back(nums[idx]);
dfs(nums, idx + 1);
res.pop_back();
dfs(nums, idx + 1);
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
dfs(nums, 0);
return ans;
}
};