LeetCode: Subsets II [091]

class Solution {
public:

    void getCombinations(vector<vector<int> >&result, vector<int>&s, vector<int>combination, int index2add, int kth, int k){
        //将s中的第index2add位上的数作为组合中的第kth个数
        combination.push_back(s[index2add]);
        if(kth==k){
            result.push_back(combination);
            return;
        }
        
        for(int i=index2add+1; i+(k-kth-1)<s.size(); i++){
            if(i!=index2add+1 && s[i]==s[i-1])continue; //去重
            getCombinations(result, s, combination, i, kth+1, k);
        }
    }

    vector<vector<int> > getSubsetK(vector<int>&s, int k){
        // 求长度为k的子集
        vector<vector<int> >result;
        vector<int> combination;
        for(int i=0; i+(k-1)<s.size(); i++){
            if(i!=0 && s[i]==s[i-1])continue;   //排重
            getCombinations(result, s, combination, i, 1, k);
        }
        return result;
    }

    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        vector<vector<int> >result;
        vector<int> emptySet;   //一定有个空集
        result.push_back(emptySet);
        
        int size=S.size();
        if(size==0)return result;
        
        sort(S.begin(), S.end());
        
        for(int k=1; k<=size; k++){
            //分别求出长度为1,2,3,...size的子集
            vector<vector<int> >subsets=getSubsetK(S, k);
            result.insert(result.end(), subsets.begin(), subsets.end());
        }
        return result;
    }
};