//需要注意的: 
//for (int i = startIndex; i < nums.size(); i++) {
//current.push_back(nums[i]);
//dfsHelper(nums, i + 1, current, results);
//current.pop_back();

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

        sort(nums.begin(), nums.end());

        vector<int> current;

        dfsHelper(nums, 0, current, results);

        return results;
    }
    // 1. definition: get a subset from nums starting from startIndex and put them into current;
    void dfsHelper(vector<int> &nums, int startIndex, vector<int>& current, vector<vector<int> >& results) {
        results.push_back(current);

        // By having a startIndex variable and only allow elements starting from startIndex to be candidates that can be chosen to form a subset, we actually eliminate duplicated subset say we have [1, 2] and we picked [1, 2] already and we have a current [2] and if [2] is allowed to pick from 0 index again, we will have [2, 1] which is a duplicate of [1, 2] and is wrong.
        // For combination and subset problem, unique results do not come from the variation of the sequence of the elements; so we enforce only ONE sequence which helps avoid duplicate results; unqiue results come from different combination of the elements; 
        for (int i = startIndex; i < nums.size(); i++) {
            current.push_back(nums[i]);
            dfsHelper(nums, i + 1, current, results);
            current.pop_back();
        }

        return;
    }
};