【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 = ; i < pow(2.0, size); i ++)

        {

            int tag = i;

            vector<int> cur;

            for(int j = size-; j >= ; j --)

            {

                if(!tag)

                    break;

                if(tag% == )

                {

                    cur.push_back(S[j]);

                }

                tag >>= ;

            }

            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 = ; i < S.size(); i ++)

            count[S[i]] ++;

        vector<int>::iterator iter = unique(S.begin(), S.end());

        S.erase(iter, S.end());

        for(int i = ; i < S.size(); i ++)

        {

            int size = ret.size();

            for(int j = ; j < size; j ++)

            {

                vector<int> newset = ret[j];

                for(int k = ; k < count[S[i]]; k ++)

                {

                    newset.push_back(S[i]);

                    ret.push_back(newset);

                }

            }

        }

        return ret;

    }

};