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

            return result;
        }
        vector <int> cur;
        dsfHelper(nums, result, cur, 0);
        return result;
    }
    void dsfHelper(vector<int> &nums, vector<vector<int>> &result, vector<int> &cur, int index) {
        result.push_back(cur);
        for (int i = index; i < nums.size(); i++) {
            cur.push_back(nums[i]);
            dsfHelper(nums, result, cur, i+1);
            cur.pop_back();
        }
    }
};