LeetCode_Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example, If S =  [1,2,2] , a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

このテーマは前のテーマの拡張で、BFSの直接MLEを続けて、そこで後に改善したアルゴリズムを使うしかなくて、コードは以下の通りです:

class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        vector <vector<int>> result(1);
        if(S.size()==0){
            return result;
        }
        
        //sort S in non-descending order
        sort(S.begin(),S.end());
        
        result.push_back(vector<int>(1,S[0]));
        int oldVal=S[0];
        int oldExtSubsets=1;
        
        for(int i=1;i<S.size();i++){
            
            //calculate the subs should be extended
            int extSubs=result.size();
            if(oldVal==S[i]){
                extSubs=result.size()-oldExtSubsets;
                oldExtSubsets+=extSubs;
            }
            else{
                oldExtSubsets=extSubs;
            }
            oldVal=S[i];
            
            //extend the subs should be extended
            int j=result.size()-1;
            for(int k=0;k<extSubs;k++){
                result.push_back(result[j-k]);
                result.back().push_back(S[i]);
            }
        }
        
        return result;
    }
};