78. Subsets-蒲公英云

78. Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

方法一：回溯法。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>>  result;  //存储最终结果
        vector<int> item;            //回溯时，产生各个子集的数组
        result.push_back(item);
        int i=0;       
        generate(i, nums,item,result);
        return result;
    }
private:
    void generate(int i,vector<int>& nums,  vector<int>& item,  vector<vector<int>> &result) 
    {
        if(i>= nums.size())
            return;
        item.push_back(nums[i]);         //添加当前元素 
        result.push_back(item);            
        generate(i+1, nums,item,result);  //第一次递归调用
        item.pop_back();                  //不添加当前元素
        generate(i+1, nums,item,result);  //第二次递归调用
    }  
};

方法二：位运算法

用到了按位&和左移运算。假设原始集合\{a, b, c\}，子集中a, b, c可能存在也可能不存在，假设1表示存在，0表示不存在。用三个二进制位分别表示a, b, c。100表示a存在，010表示b存在，001表示c存在。这三种情况都可以通过1左移得到。
由组合数学可知，三个元素的集合，其子集有2^3种情况。遍历其中每一种情况，分别和100,010，001按位&运算，如果结果为真，则子集中包含对应元素，否则不包含。
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>>  result;  //存储最终结果
        int count = pow(2,nums.size());
        for(int i=0; i<count; i++)
        {
            vector<int> item;
            for(int j=0; j<nums.size(); j++)
            {  
                if(i & (1<<j))
                {
                    item.push_back(nums[j]);
                }
            }
            result.push_back(item);
        }
        return result;
    }    
};