学步园

题目如下:

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],
  []
]

分析如下：

和上一题基本一样，区别在于这道题目的输入集合中的元素可能有重复，要求输出的子集合中过滤掉重复。可以先得到一个有重复的结果，再用个set或者hash滤重(使用0(N)空间复杂度)

我的代码:

第一版本，先迭代再滤重版本

// 先迭代再滤重
class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        int length=(int)S.size();
        vector<vector<int>> res(1);
        if(length==0)
            return res;
        std::sort(S.begin(), S.end());
        for(int i=0;i<S.size();++i){
            int j=(int)res.size();
            while(--j>=0){
                res.push_back(res[j]);
                res.back().push_back(S[i]);
            }
        }
        set<vector<int> > filter_set;
        for(int i=0;i<res.size();++i)
            filter_set.insert(res[i]);
        res.clear();
        for(set<vector<int> >::iterator it=filter_set.begin();it!=filter_set.end();it++)
            res.push_back(*it);
        return res;
    }
};

第二版本，先递归再滤重版本

//先递归再滤重
class Solution {
public:
        set<vector<int> > subsets_(vector<int> &S, int i){
        if(i==-1){
            vector<int> set_tmp;
            set<vector<int> > set_set_tmp;
            set_set_tmp.insert(set_tmp);
            return set_set_tmp;
        }
        set<vector<int> >  set_vec_tmp = subsets_(S,i-1);
        set<vector<int> >  set_vec_out = set_vec_tmp;
        set<vector<int> >::iterator set_vec_it=set_vec_tmp.begin();
        for(set_vec_it=set_vec_tmp.begin();set_vec_it!=set_vec_tmp.end();set_vec_it++){
            vector<int> vec_tmp=*set_vec_it;
            vec_tmp.push_back(S[i]);
            std::sort(vec_tmp.begin(),vec_tmp.end());
            set_vec_out.insert(vec_tmp);
        }
        return set_vec_out;
    }
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        int length=(int)S.size();
        vector<vector<int>> res;
        set<vector<int>> tmp;
        if(length==0)
            return res;
        length--;
        tmp=subsets_(S,length);
        for(set<vector<int> >::iterator it=tmp.begin();it!=tmp.end();it++){
            vector<int> small_vec=*it;
            res.push_back(small_vec);
        }
        return res;
    }
};

第三版本

我还没怎么看懂，不使用set不使用hash直接滤重，官网上看到的答案如下。

//不使用set或者hash直接滤重
class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function            
        vector<int> path;
        vector<vector<int> > result;

        sort(S.begin(), S.end());
        sub(S, 0, path, result);
        return result;
    }

    void sub(vector<int> &s, int begin, vector<int> &path, vector<vector<int> > &result) {
        result.push_back(path);

        for (int i = begin; i < s.size(); ++i) {
            if (i != begin && s[i] == s[i - 1]) continue;

            path.push_back(s[i]);
            sub(s, i + 1, path, result);
            path.pop_back();
        }
    }
};

参考资料：

(1) http://discuss.leetcode.com/questions/253/subsets