78. Subsets
题目描述：给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）
解法一：使用深度优先遍历dfs，分为两种：一种是递归；另一种是循环。
//使用递归进行深度优先遍历
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
vector<int> sub;
dfs(nums,0,sub,res);
return res;
}
void dfs(vector<int>& nums,int start,vector<int>& sub,vector<vector<int>>& res){
res.push_back(sub);//推入当前子集
for(int i=start;i<nums.size();i++){
sub.push_back(nums[i]);
dfs(nums,i+1,sub,res);
sub.pop_back();
}
}
};
//使用循环进行深度优先遍历
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> subs(1,vector<int>());
for(int i=0;i<nums.size();i++){
int n=subs.size();
for(int j=0;j<n;j++){
subs.push_back(subs[j]);
subs.back().push_back(nums[i]);
}
}
return subs;
}
};
方法二：位运算方式 高中数学可知，对于一个有n个不同元素的子集共有$2^n$个子集。这是因为对于每个子集，每个元素可以出现或者不出现，故总共子集的个数为$2^n$个。
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
int n = pow(2, nums.size());
vector<vector<int>> subs(n, vector<int>());
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < n; j++) {
if ((j >> i) & 1) {
subs[j].push_back(nums[i]);
}
}
}
return subs;
}
};