力扣每日一题78：子集
题目描述：
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0] 输出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10nums中的所有元素 互不相同
通过次数
691.2K
提交次数
851.9K
通过率
81.1%
思路和题解：
一、递归
这题思路和第77题一样，第77题是从n个数中选k个数，对于每个样例，n和k都是固定的。而这题的不同就是k可以是[0,n]的任意数。我们还是可以用递归的方法，n层的递归，从第0层开始，每次递归的数字都可放可不放，递归到第n+1层时就退出。
代码：
class Solution {
public:void dfs(vector<vector<int>> &ans,vector<int> &temp,int depth,int n,vector<int> nums){if(depth==n){ans.emplace_back(temp);return ;}//选temp.emplace_back(nums[depth]);dfs(ans,temp,depth+1,n,nums);//不选temp.pop_back();dfs(ans,temp,depth+1,n,nums);}vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> ans;vector<int> temp;dfs(ans,temp,0,nums.size(),nums);return ans;}
};二、二进制
前面提到的对于[1,n]的每一个数都有选或不选两种状态，既然是每个元素都有两种状态，我们就可以用二进制的方法。数组中的每个元素对于二进制中的一个位，如果选的话就对应0，如果不选的话对应1，每一个位都确定好后形成一个二进制数x，范围在[0,2^n-1]。所以，我们只需要对[0,2^n-1]进行遍历，对于每一个数都取出它的二进制的每一位，对于第i位数，如果是1，就把nums[i]加入幂集中，否则看下一个位。
代码：
//二进制
class Solution{
public:vector<vector<int>> subsets(vector<int>& nums){int n=pow(2,nums.size());vector<vector<int>> ans;for(int i=0;i<n;i++){int x=i;vector<int> temp;int j=0;while(x){if(x%2==1) temp.emplace_back(nums[j]);x/=2;j++;}ans.emplace_back(temp);}return ans;}
};