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;

    }

};