1. 090

subsets-ii

2. 算法

http://www.cnblogs.com/grandyang/p/4310964.html

• O(2^n)

3. 代码

3.1 递归的解法

class Solution{
public:
    vector<vector<int> >  subsetWithDup(vector<int>& S){
        vector<vector<int> > res;
        vector<int> out;
        sort(S.begin(),S.end());
        getSubsets(S,0,out,res);
        return res;
    }
private:
    void getSubsets(vector<int>& S,int pos,vector<int>& out,vector<vector<int> >& res){
        res.push_back(out);
        for(int i=pos;i<S.size();++i){
            out.push_back(S[i]);
            getSubsets(S,i+1,out,res);
            out.pop_back();
            while(S[i]==S[i+1]) ++i;
            //跳过树中为x的节点
        }
    }
};

3.2 优化

 // Non-recursion
class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        vector<vector<int> > res(1);
        sort(S.begin(), S.end());
        int size = 1, last = S[0];
        for (int i = 0; i < S.size(); ++i) {
            if (last != S[i]) {
                last = S[i];
                size = res.size();
            }
            int newSize = res.size();
            for (int j = newSize - size; j < newSize; ++j) {
                res.push_back(res[j]);
                res.back().push_back(S[i]);
            }
        }
        return res;
    }
};