Fork me on GitHub

Subsets II

Posted on

Description

https://leetcode.com/problems/subsets-ii/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int> > ret;
        unordered_map<int, int> counter;
        for (int i = 0; i < nums.size(); i++) counter[nums[i]] += 1;
        unordered_map<int, int>::iterator iter = counter.begin(); 
        vector<int> current;
        this->getSet(counter, current, iter, ret);
        return ret;
    }
    
    void getSet(unordered_map<int, int>& counter, vector<int>& current, \
        unordered_map<int, int>::iterator iter, vector<vector<int>>& ret) {
        ret.push_back(current);
        if (iter == counter.end()) return;
        for (auto it = iter; it != counter.end(); it++) {
            int count = it->second;
            for (int i = 0; i < count; i++) {
                current.push_back(it->first);
                auto nextIter = next(it, 1);
                this->getSet(counter, current, nextIter, ret);
            }
            for (int i = 0; i < count; i++) current.pop_back();
        }
        return;
    }
};