<LeetCode OJ> 78 / 90 Subsets (I / II)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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

[

  [3],

  [1],

  [2],

  [1,2,3],

  [1,3],

  [2,3],

  [1,2],

  []

]

分析：

的题目意思基本一样，主要差别在于还须要对不同的len的子数组进行回溯，所以回溯法终于确定答案的方式不一样。

（本题是用len作为回溯时确定答案的根据）

class Solution {

public:

    void dfs(vector<int>& nums, vector<int> &subres, int start, int len)//使用引用，有利于防止内存大爆炸

    {

        if (subres.size() == len)//已经获得答案。而且回溯

        {

            result.push_back(subres);

            return;//回溯

        }

        for (int i = start; i < nsize; i++)

        {

            subres.push_back(nums[i]);

            dfs(nums, subres, i + 1, len);

            subres.pop_back(); // 完毕一个解后去掉末尾元素 ，准备下一次回溯寻找答案

        }

    }

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

        nsize=nums.size();

        if ( nsize == 0)

            return result;

        sort(nums.begin(),nums.end()); //一，先排序

        vector<int> subres;

        for(int len=0; len<=nums.size() ;len++)//二，对不同长度的子数组进行回溯

            dfs(nums, subres, 0, len);

        return result;

    }

private:

    vector<vector<int > > result;

    int nsize;

};

Total Accepted: 62569 Total
Submissions: 208285 Difficulty: Medium

Given a collection of integers that might contain duplicates, nums, 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 nums = [1,2,2] , a solution
is:

[

  [2],

  [1],

  [1,2,2],

  [2,2],

  [1,2],

  []

]

分析：

比上面的代码多加入一个同样组合不要的回溯条件就可以，只是代码的速度尽然打败了0.89%，也就是说极慢的速度。感觉不会再爱了。

class Solution {

public:

    void dfs(vector<int>& nums, vector<int> &subres, int start, int len)//使用引用，有利于防止内存大爆炸

    {

        if (subres.size() == len)//已经获得答案。而且回溯

        {

            if(!isSameVec(subres))  //已经出现过的组合不要。

                result.push_back(subres);

            return;//回溯

        }

        for (int i = start; i < nsize; i++)

        {

            subres.push_back(nums[i]);

            dfs(nums, subres, i + 1, len);

            subres.pop_back(); // 完毕一个解后去掉末尾元素 。准备下一次回溯寻找答案

        }

    }

    bool isSameVec(vector<int> &sub)

    {

        for(int i=0;i<result.size();i++)

        {

            if(result[i]==sub)

                return true;

        }

        return false;

    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {

        nsize=nums.size();

        if ( nsize == 0)

            return result;

        sort(nums.begin(),nums.end()); //一，先排序

        vector<int> subres;

        for(int len=0; len<=nums.size() ;len++)//二，对不同长度的子数组进行回溯

            dfs(nums, subres, 0, len);

        return result;

    }

private:

    vector<vector<int > > result;

    int nsize;

};

学习别人的算法：

class Solution {

public:

    void dfs(vector<int> &s, int index, vector<int> &subset, vector<vector<int>> &res)

    {

        res.push_back(subset);

        for(int i = index; i< s.size(); i++)

        {

            if(i!=index && s[i]==s[i-1])

                continue;

            subset.push_back(s[i]);

            dfs(s,i+1,subset,res);

            subset.pop_back();

        }

    }

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

        // Note: The Solution object is instantiated only once.

        vector<vector<int>> result;

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

        vector<int> subset;

        dfs(S,0,subset,result);

        return result;

    }

};