【LeetCode】78. Subsets (2 solutions)

Subsets

Given a set of distinct integers, 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,3], a solution is:

[

  [3],

  [1],

  [2],

  [1,2,3],

  [1,3],

  [2,3],

  [1,2],

  []

]

解法一：

遍历S.size()位数的所有二进制数，1代表对应位置的元素在集合中，0代表不在。

一共2^n种情况。

详细步骤参照Subsets II

class Solution {

public:

    vector<vector<int> > subsets(vector<int> &S) {

        vector<vector<int> > result;

        int size = S.size();

        for(int i = ; i < pow(2.0, size); i ++)

        {//2^size subsets

            vector<int> cur;

            int tag = i;

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

            {//for each subset, the binary presentation has size digits

                if(tag% == )

                    cur.push_back(S[j]);

                tag >>= ;

                if(!tag)

                    break;

            }

            sort(cur.begin(), cur.end());

            result.push_back(cur);

        }

        return result;

    }

};

解法二：

遍历所有元素，记当前元素为S[i]

遍历当前所有获得的子集，记为ret[j]

将S[i]加入ret[j]，即构成了一个新子集。

详细步骤参照Subsets II

class Solution {

public:

    vector<vector<int> > subsets(vector<int> &S) {

        sort(S.begin(), S.end());

        vector<vector<int> > ret;

        vector<int> empty;

        ret.push_back(empty);

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

        {

            int size = ret.size();

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

            {

                vector<int> newset = ret[j];

                newset.push_back(S[i]);

                ret.push_back(newset);

            }

        }

        return ret;

    }

};

巴特西

【LeetCode】78. Subsets (2 solutions)

最新文章

热门文章