78. Subsets

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

不用再多描述了，就是求子集合

解法 :  

一開始要先將空集合加入，然後對於array做排序(第一題的邏輯其實是不需要，但是題目的解答中{2,1}跟{1,2}不算同一集合), 接下來開始做DFS

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
       
       vector<vector<int>> ans;
       vector<int> sub{};
       
       //先將空集合加入
       ans.push_back(sub);
       //做排序
       sort(nums.begin(), nums.end());
       subsetsDFS(nums, sub, 0, ans);
       return ans; 
    }
    
    void subsetsDFS(const vector<int>& nums, vector<int> &sub, int start, vector<vector<int>> &output)
    {
        for(int i = start; i < nums.size(); i++)
        {
           sub.push_back(nums[i]);    
           output.push_back(sub);
           subsetsDFS(nums, sub, i+1, output);
           //找過的給清掉
           sub.pop_back();
        }
    }
};