题目描述：

给你一个整数数组 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] <= 10
• nums 中的所有元素 互不相同

通过次数

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;}
};