Subsets II

<-M 90> Subsets II

// Method 1
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> result(1);
        int previous_size = 0;
        for(int i = 0; i < nums.size(); i++) {
            int size = result.size();
            for(int j = 0; j < size; j++) {
                if(i == 0 || nums[i] != nums[i - 1] || j >= previous_size) {
                    result.push_back(result[j]);
                    result.back().push_back(nums[i]);
                }
            }
            previous_size = size;
        }
        return result;
    }
};

// Method 2
class Solution {
private:
    void dfs(const vector<int> &nums, vector<int>::iterator start, vector<int> &path,
           vector<vector<int>> &result) {
        result.push_back(path);

        for(auto i = start; i < nums.end(); i++) {
            if(i != start && *i == *(i - 1))
                continue;
            path.push_back(*i);
            dfs(nums, i + 1, path, result);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;
        vector<int> path;
        dfs(nums, nums.begin(), path, result);
        return result;
    }
};