Leetcode 78: subsets

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

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

DFS遍历一颗dfs树获得所有解，但是结果要求non-descending order，所以需要先对数列进行排序。

class Solution {
private:
    void DFS(vector<int> nums, vector<vector<int>> &rst, vector<int> solu, int cur) {
        if (cur == nums.size()) {
            rst.push_back(solu);
            return;
        }
        //add a
        solu.push_back(nums[cur]);
        DFS(nums, rst, solu, cur+1);
        solu.pop_back();
        //don't add a
        DFS(nums, rst, solu, cur+1);
        return;
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> rst;
        vector<int> solu;
        //sanity check
        if (nums.size() == 0) return rst;
        DFS(nums, rst, solu, 0);
        return rst;
    }
};