78. Subsets

  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],
    []
  ]

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res(1, vector<int>());

        for(int i = 0; i < nums.size(); i++){
            int len = res.size();
          //从nums[0]到nums[i - 1]得到Subsets，将nums[i]插入到上面的结果中,遍历Subsets
            for(int j = 0; j < len; j++){
                res.push_back(res[j]);
                res.back().push_back(nums[i]);
            }
        }
        return res;
    }
};

还可以利用bit位来表示子集，例如[1, 2, 3],分别用一个二进制的数来代表上面的各位是否存在,例如空集就可以表示为(000)b，[100]b就表示[1],
(111)b表示[1,2,3]

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int len = nums.size();

        int subset_num = (1<<len);

        vector<vector<int>> res;
        for(int i = 0; i < subset_num; i++){
            vector<int> one_subset;
            for(int j = 0; j < len; j++){
                if((i>>j) & 1){
                    one_subset.push_back(nums[j]);
                }
            }
            res.push_back(one_subset);
        }
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int len = nums.size();

        int subset_num = (1<<len);

        vector<vector<int>> res(subset_num, vector<int>());
        for(int i = 0; i < subset_num; i++){
            for(int j = 0; j < len; j++){
                if((i>>j) & 1){
                    res[i].push_back(nums[j]);
                }
            }
        }
        return res;
    }
};

//使用回溯法
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> subset;
        vector<vector<int>> subsets;

        genSubset(nums, 0, subset, subsets);
        return subsets;
    }
private:
    void genSubset(vector<int>  &arr, int level, vector<int> &subset, vector<vector<int>> &res){
      //注意将下面的语句换成注释的语句会怎样
      /*
       if(level == arr.size()){
         res.push_back(subset);
         return;
       }
       结果为:
       Your input:
       [1,2,3]
       Your answer
       [1,2,3],[1,3],[2,3],[3]]
       Expected answer
       [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
       不会出现
       */
        res.push_back(subset);

        for(int i = level; i < arr.size(); i++){
            subset.push_back(arr[i]);
            genSubset(arr, i + 1, subset, res);
            subset.pop_back();
        }
    }
};