lintcode---子集（带重复元素和不带重复元素的两种解法）

115 阅读 0 评论 76 点赞

我是靠谱客的博主狂野烤鸡，最近开发中收集的这篇文章主要介绍lintcode---子集（带重复元素和不带重复元素的两种解法），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述：
给定一个含不同整数的集合，返回其所有的子集。

注意事项：
子集中的元素排列必须是非降序的，解集必须不包含重复的子集。

样例：
如果 S = [1,2,3]，有如下的解：

[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

思路分析（对于没有重复元素）：
我们可以先看一个例子[1]、[1,2]、[1,2,3]这三个的子集分别是什么？
[1]的子集是[1]、[]
[1,2]的子集是[1]、[1，2]、[2]、[]
[1,2,3]的子集是[1]、[1，2]、[2]、[1，3]、[1，2，3]、[2，3]、[3]、[]

我们发现[1,2,3]是在[1,2]的所有子集尾部添加了3之后合并[1,2]的子集就是[1,2,3]的子集。
[1,2]也是在[1]的所有子集尾部添加了2，然后合并[1]的子集就是[1,2]的子集。

通过上面的例子，我们可以发现我们可以通过n次循环，每一次在上一次的基础上进行操作就可以了。

代码详解：

class Solution {
public:
    /*
     * @param nums: A set of numbers
     * @return: A list of lists
     */
    vector<vector<int>> subsets(vector<int> &nums) {
        // write your code here
        vector<vector<int>>res;
        if(nums.size()==0)
        {
            res.push_back(nums);
            return res;
        }

        //vector<vector<int>>res;
        vector<int>temp;
        temp.push_back(nums[0]);
        res.push_back(temp);
        temp.clear();

        for(int i=1;i<nums.size();i++)
        {
            int length=res.size();

            for(int j=0;j<length;j++)
            {
                temp.assign(res[j].begin(),res[j].end());
                temp.push_back(nums[i]);
                res.push_back(temp);
                temp.clear();
            }
            temp.push_back(nums[i]);
            res.push_back(temp);
            temp.clear();
        }
        res.push_back(temp);
        return res;
    }
};

思路分析（对于有重复元素）：
我们还是先看一个例子[1]、[1,1]、[1,2,2]这三个的子集分别是什么？
[1]的子集是[1]、[]
[1,1]的子集是[1]、[1，1]、[]
[1,2]的子集是[1]、[1，2]、[2]、[]
[1,2,2]的子集是[1]、[1，2]、[2]、[1，2，2]、[2，2]、[]
通过上面的我们发现当2跟2重复时，其只在[1,2]中2添加的子集[1，2]、[2]的尾部上添加上2，得到[1，2，2]、[2，2]，将其与[1,2]的子集合并，这样就得到了[1,2,2]的子集。
同理，[1,1]我们将[1]添加的子集看作是[1]，这样其就在[1]的后面添加上1，两个合并就得到[1，1]的子集。

通过上面的例子我们发现，当出现两个重复的数字时，后面的一个数字只在上一个数字增加的子集上进行操作，而不是对所有的进行操作。

代码详解：

class Solution {
public:
    /*
     * @param nums: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int>> subsetsWithDup(vector<int> &nums) {
        // write your code here
        vector<vector<int>>res;

        if(nums.size()==0)
        {
            res.push_back(nums);
            return res;
        }

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

        vector<int>temp;
        temp.push_back(nums[0]);
        res.push_back(temp);
        temp.clear();
        int *count=new int[nums.size()+1];
        count[0]=1;

        for(int i=1;i<nums.size();i++)
        {
            if(nums[i]==nums[i-1])
            {
                int length=count[i-1];
                count[i]=length;

                cout<<"length is "<<length<<" "<<res.size()<<endl;
                //cout<<res.size()-1<<" "<<res.size()-1-length<<endl;
                int n=res.size()-length;
                //cout<<n-1<<endl;
                for(int j=res.size()-1;j>n-1;j=j-1)
                {
                    cout<<"sunshine"<<endl;
                    temp.assign(res[j].begin(),res[j].end());
                    printvector(temp);
                    temp.push_back(nums[i]);
                    //printvector(temp);
                    res.push_back(temp);
                    temp.clear();
                    printvector2D(res);


                }
                cout<<"sunshine1995"<<endl;
            }
            else{
                int length=res.size();
                count[i]=length+1;
                for(int j=0;j<length;j++)
                {
                    temp.assign(res[j].begin(),res[j].end());
                    temp.push_back(nums[i]);
                    res.push_back(temp);
                    temp.clear();
                }
                temp.push_back(nums[i]);
                res.push_back(temp);
                temp.clear();
                printvector2D(res);
            }

        }

        res.push_back(temp);
        return res;
    }

    void printvector(vector<int> res)
    {
        for(int i=0;i<res.size();i++)
        {
            cout<<res[i]<<" ";
        }
        cout<<endl;

    }
    void printvector2D(vector<vector<int>> res)
    {
        for(int i=0;i<res.size();i++)
        {
            cout<<"[";
            for(int j=0;j<res[i].size();j++)
            {
                cout<<res[i][j]<<" ";
            }
            cout<<"]"<<endl;
        }
    }
};