Subsets II

• Time : $O(2^n)$
• Space : $O(2^n)$

void helper(vector<vector<int>>& res, vector<pair<int,int>>& A, int p, vector<int>& now) {
    if(p == A.size()) res.push_back(now);
    else {
        helper(res,A,p+1,now);
        auto [n,c] = A[p];
        for(int i = 0; i < c; i++) {
            now.push_back(n);
            helper(res,A,p+1,now);
        }
        while(!now.empty() and now.back() == n) now.pop_back();
    }
}
vector<vector<int>> Solution::subsetsWithDup(vector<int> &A) {
    unordered_map<int,int> freq;
    for(auto a : A) freq[a]++;
    vector<pair<int,int>> AA;
    for(auto [k,v] : freq) AA.push_back({k,v});
    sort(begin(AA), end(AA));
    vector<vector<int>> res;
    helper(res,AA,0,vector<int>() = {});
    sort(begin(res),end(res));
    return res;
}