LeetCode 78. 子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

 1 class Solution {
 2 public:
 3     int n;
 4     vector<vector<int>> ans;
 5     vector<int> v;
 6     vector<vector<int>> subsets(vector<int>& nums) {
 7         n = nums.size();
 8         if(n == 0)
 9         {
10             ans.push_back(v);
11         }
12         else
13             dfs(0,nums);
14         return ans;
15     }
16     void dfs(int x,vector<int>& nums)
17     {
18         if(x == n)
19         {
20             ans.push_back(v);
21             return ;
22         }
23         ans.push_back(v);
24         for(int i = x;i < n;i++)
25         {
26             v.push_back(nums[i]);
27             dfs(i + 1,nums);
28             v.pop_back();
29         }
30     }
31 };

 1 class Solution {
 2 public:
 3     vector<vector<int>> subsets(vector<int>& nums) {
 4     vector<vector<int>> res;
 5     res.push_back({});
 6     if(nums.size()==0) return res;
 7     for(auto i:nums)
 8     {
 9         int k=res.size();
10         vector<vector<int>> tmp(res);
11         for(int j=0;j<k;j++)
12         {
13             tmp[j].push_back(i);
14             res.push_back(tmp[j]);
15         }
16         
17     }
18     return res;
19     }
20 };

 1 class Solution {
 2 public:
 3     vector<vector<int>> subsets(vector<int>& nums) {
 4         vector<vector<int>> ret;
 5         ret.push_back({});
 6         int size=nums.size();
 7         int subsize=pow(2,size);
 8         int hash=1;
 9         while(hash<subsize){
10             vector<int> temp;
11             for(int k=0;k<size;k++) {
12                 int a=1<<k;
13                 if(a&hash) {
14                     temp.push_back(nums[k]);
15                 }
16             }
17             ret.push_back(temp);
18             hash++;
19         }
20         return ret;
21     }
22 };