78. Subsets

problem description

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

algorithm thought

类似上一题得到组合，只不过这里需要得到所有大小的组合。只需要改变回溯法中，将中间结果push到res的位置，在进入下一个函数的时候就push，而不是在递归基的时候，这样就能到达遍历的效果。

code

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> tmp;
        res.push_back(tmp);
        res.push_back(nums);
        help(res,tmp,nums,0);
        return res;
    }
    void help(vector<vector<int>>& res,vector<int>&tmp,vector<int>& nums,int pos){
        if(tmp.size()==nums.size()-1)
            return;
        for(int i=pos;i<nums.size();++i){
            tmp.push_back(nums[i]);
            res.push_back(tmp);
            help(res,tmp,nums,i+1);
            tmp.pop_back();
        }
    }
};

algorithm analysis

时间复杂度是O(2^n),对于每一个数，都能选择是放入或者不放入最后数组