Subsets

题目：

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

Elements in a subset must be in non-descending order.

Example

If S = [1,2,3], a solution is: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

接口：

class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int> > subsets(vector<int> &nums) {

    }
};

分析：

既然他说find all possible subsets，就给他来个dfs的traversal模板。注意的是，这道题目提到nums中没有重复的数字，所以比较简单，不用考虑去重的问题。

解法：

class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    void dfs(vector<int> nums, 
                vector<int> instance, 
                vector<vector<int> >& res, 
                int start) {

        res.push_back(instance);

        for (int i = start; i < nums.size(); i++) {
            instance.push_back(nums[i]);
            dfs(nums, instance, res, i + 1);
            instance.pop_back();
        }

    } 

    vector<vector<int> > subsets(vector<int> &nums) {
        if (nums.size() == 0) {
            return vector<vector<int> >();
        }

        sort(nums.begin(), nums.end() );
        vector<vector<int> > res;
        vector<int> instance;
        dfs(nums, instance, res, 0);

        return res;
    }
};