题解 | #集合的所有子集#

题目描述：现在有一个没有重复元素的整数集合S，求S的所有子集
        注意：你给出的子集中的元素必须按升序排列，给出的解集中不能出现重复的元素
示例1
        输入：[1,2,3]
        返回值：[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
思路：要想求得n个非重复元素的子集，还要按照升序排列，那么简单直接地先把数组排序；对于长度为1的数组，它的子集为[]和[val]，而当数组长度大于1时，发现子集存在这样一个规律：长度为n的数组的子集=长度为n-1的数组的子集+以该子集添加第n个元素后的子集，(顾名思义，同时浅显易懂，其实就是包含第n个元素的子集 与 不包含第n个元素的子集)。因此考虑使用递归，要想求长度为n的数组的子集，先取出最后一个元素，求得前n-1个元素的子集RESn1，然后利用RESn1子集生成包含第n个元素的子集RESn（即RESn1中的每个子集分别添加第n个元素即可），最后按照子集长度依次排列并排序进入RES，返回结果RES。

class Solution {
public:

    vector<vector<int> > subsets(vector<int> &S) {//本质是递归
        vector<vector<int> > RES;
        sort(S.begin(),S.end());//先进行排序
        int n = S.size();
        if(n == 1)
        {
            vector<int> res;
            RES.push_back(res);
            res.push_back(S[0]);
            RES.push_back(res);
        }
        else
        {
            vector<int> R;
            for(int i=0;i<n-1;i++)
                R.push_back(S[i]);//去除最后一个元素的数组
            int last = S[n-1];//获取最后一个元素值
            vector<vector<int> > RESn1 = subsets(R);//不包含最后一个元素的子集
            int s = RESn1.size();
            vector<vector<int> > RESn;//利用不包含最后一个元素的子集来获得包含最后一个元素的子集；
            for(int i=0;i<RESn1.size();i++)
            {
                vector<int> temp = RESn1[i];
                temp.push_back(last);
                RESn.push_back(temp);
            }
            int len=0,q=0;
            vector<vector<int> > RESlen;//各个长度的子集（如长度为0、1、2.。，n的子集）
            while(len<=n)
            {
                while(q<s)
                {
                    if(RESn1[q].size() == len)
                        RESlen.push_back(RESn1[q]);
                    if(RESn[q].size() == len)
                        RESlen.push_back(RESn[q]);
                    q++;
                }
                sort(RESlen.begin(),RESlen.end());
                for(int j=0;j<RESlen.size();j++)
                {
                    RES.push_back(RESlen[j]);
                }
                RESlen.clear();
                len++;
                q=0;
            }
        }
        return RES;
    }
};