90-Subsets-2

Subsets2.cpp

class Solution {
private:
    vector<vector<int>> powerset;
    vector<int> subset;
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end()); //change 1
        
        backtrack(nums, 0);
        return powerset;
    }
    
    void backtrack(vector<int>& nums, int start){
        powerset.push_back(subset);
        
        for(int i = start; i < nums.size(); i++){
            if(i > start && nums[i] == nums[i-1]) continue; //change 2, skip over duplicates
            
            subset.push_back(nums[i]);
            backtrack(nums, i+1);
            
            subset.pop_back();
        }
    }
};