【LeetCode】90. Subsets II (2 solutions)

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

解法一：

举例说明我的算法：

设S={1,2,2}，则size=3

在不考虑重复的情况下，子集共有2^3=8个

分别为：

【1,2,2】

   0,0,0  {}

   0,0,1  {2}

   0,1,0  {2}

   0,1,1  {2,2}

   1,0,0  {1}

   1,0,1  {1,2}

   1,1,0  {1,2}

   1,1,1  {1,2,2}

1表示对应位的元素存在于集合中，0表示不存在。

因此只要从0遍历到2^size - 1，如果对应位为1，则将S中相应元素加入当前集合。

对于Note的两点要求：

1、sort函数对集合排序

2、使用map去重，存在即去除。

class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        vector<vector<int> > result;
        map<vector<int>, bool> m;
        int size = S.size();
        for(int i = 0; i < pow(2.0, size); i ++)
        {
            int tag = i;
            vector<int> cur;
            for(int j = size-1; j >= 0; j --)
            {
                if(!tag)
                    break;
                if(tag%2 == 1)
                {
                    cur.push_back(S[j]);
                }
                tag >>= 1;
            }
            sort(cur.begin(), cur.end());
            if(m.find(cur) == m.end()) 
            {
                m[cur] = true;
                result.push_back(cur);
            }
        }
        return result;
    }
};

解法一额外开辟了map，因此占用了大量的空间。

可以这样来看。

后加入的元素，需要加入全部已有的集合，并且考虑重复。

再次考虑S={1,2,2}，先排序。

首先加入空集{}

对于元素1，需要加入{}，成为新的集合{1}

对于元素2，需要加入{}和{1}，成为新的集合{2}和{1,2}。考虑重复，再产生新集合{2,2}和{1,2,2}。

class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        vector<vector<int> > ret;
        vector<int> empty;
        ret.push_back(empty);
        
        sort(S.begin(), S.end());
        unordered_map<int, int> count;
        for(int i = 0; i < S.size(); i ++)
            count[S[i]] ++;
        vector<int>::iterator iter = unique(S.begin(), S.end());
        S.erase(iter, S.end());
        for(int i = 0; i < S.size(); i ++)
        {
            int size = ret.size();
            for(int j = 0; j < size; j ++)
            {
                vector<int> newset = ret[j];
                for(int k = 0; k < count[S[i]]; k ++)
                {
                    newset.push_back(S[i]);
                    ret.push_back(newset);
                }
            }
        }
        return ret;
    }
};