Leetcode 78. Subsets

78. Subsets

Total Accepted: 106996
Total Submissions: 323591
Difficulty: Medium

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

思路：

方法一：

先求出子集的个数subset_num=2^(nums.size())。对于每个元素，每个子集只有2种可能：包含或不包含，那么只要按照顺序添加对应元素就可以了。
j表示的是第j个子集，j可以被表示成subset_num二进制位，第i位表示的是第j个子集包含元素nums[i]的情况：j的第i位为1表示当前子集包含nums[i]；j的第i位为0表示当前子集不包含nums[i]。

方法二：

回溯法构造子集，subsets(vector<vector<int> > &res,vector<int> nums,int cur)含义是当前res中未有包含nums[cur]的子集，下面要建立所有包含元素nums[cur]的子集。

方法三：

以[1,2,3]为例：

初始状态：[]

添加第1个元素：[],[1]

添加第2个元素：[],[1],[2],[1,2]

添加第3个元素：[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]

添加第i个元素形成的子集情况S_i，那么有S_i=S_i-1U(S_i-1中每个子集添加nums[i]后形成的子集群)

代码：

方法一：

 1 class Solution {
 2 public:
 3     vector<vector<int> > subsets(vector<int>& nums) {
 4         int n=nums.size(),subset_num=pow(2,n);
 5         vector<vector<int> > res(subset_num,vector<int>{});
 6         for(int i=0;i<n;i++){
 7             for(int j=0;j<subset_num;j++){
 8                 if(j>>i&1){
 9                     res[j].push_back(nums[i]);
10                 }
11             }
12         }
13         return res;
14     }
15 };

方法二：

 1 class Solution {
 2 public:
 3     vector<vector<int> > res;
 4     vector<int> v;
 5     void subsets(vector<vector<int> > &res,vector<int> nums,int cur){
 6         res.push_back(v);
 7         for(int i=cur;i<nums.size();i++){
 8             v.push_back(nums[i]);
 9             subsets(res,nums,i+1);
10             v.pop_back();
11         }
12     }
13     vector<vector<int> > subsets(vector<int>& nums) {
14         subsets(res,nums,0);
15         return res;
16     }
17 };

方法三：

 1 class Solution {
 2 public:
 3     vector<vector<int> > subsets(vector<int>& nums) {
 4         int n=nums.size(),subset_num=0;
 5         
 6         vector<vector<int> > res(1,vector<int>{});
 7         for(int i=0;i<n;i++){
 8             subset_num=res.size();
 9             for(int j=0;j<subset_num;j++){
10                 res.push_back(res[j]);
11                 res.back().push_back(nums[i]);
12             }
13         }
14         return res;
15     }
16 };