class Solution {
public:
    /*
     * @param nums: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int>> subsetsWithDup(vector<int> nums) {
        // write your code here
        sort(nums.begin(), nums.end());
        vector<int> soFar;
        vector<vector<int>> results;
        findAllSubsets(nums, 0, soFar, results);
        return results;
    }

    // find all the subsets starting with nums[startIndex] and put them into results;
    void findAllSubsets(vector<int>& nums, int startIndex, vector<int>& soFar, vector<vector<int>>& results) {
        results.push_back(soFar);
        // any elements in nums can serve as the 1st element in the subset so we iterate over all the elements and to set them as the 1st element in the subsets;
        for (int i = startIndex; i < nums.size(); i++) {
            if (i != startIndex && nums[i] == nums[i - 1]) {
                continue;
            }
            soFar.push_back(nums[i]);
            findAllSubsets(nums, i + 1, soFar, results);
            soFar.pop_back();
        }

        return;
    }
};