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

题目：集合中的所有子集

描述：现在有一个没有重复元素的整数集合S，求S的所有子集
注意：你给出的子集中的元素必须按升序排列，给出的解集中不能出现重复的元素。

示例1：输入：[1,2,3]，返回值：[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

解法一：
思路分析：初读题目，我们可以看出来这是初中的一道数学题目，题目要求输出S的所有子集，这里我们想到首先肯定是空子集，首先将空子集传入最终设计的容器res中，题目要求所有的子集必须按照升序排列，所以我们可以调用sort()函数，首先就对该集合进行元素排序，然后挨个进行输出，用i表示数位，当i等于1的时候，输出子集数量为1的子集，依次类推，构建一个循环，实际上相当于，用暴力法将每个符合条件的子集挨个添加到容器当中。

实例分析：输入：[1,2,3]

其中按位数输出子集的代码为：

	void subset(vector&S, vector &vec, vectorsub, int start, int k) {
        if (k == sub.size()){//当循环满足条件后，存储进一个集合当中
            vec.push_back(sub);
            return;
        }
        for (int i = start; i < S.size(); ++i) {//存储的顺序 
            sub.push_back(S[i]); 
            subset(S, vec, sub, i+1, k); 
            sub.pop_back(); 
    } 
}

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int>> res;//设置最终存放的对象
        int size = S.size();//S中包含多少元素
        if (size == 0)
            return res;
        vector<int> sub;
        sort(S.begin(), S.end());//题目要求按顺序排放
        res.push_back(sub);//空子集是所有集合的子集
        for (int i = 1; i <= S.size(); ++i) {//i表示位数，i = 1时表示返回一位的子集
            subset(S, res, sub, 0, i);
        }
        return res;
    }
    void subset(vector<int> &S, vector<vector<int> > &vec, vector<int> sub, int start, int k) {
        if (k == sub.size()){//当循环满足条件后，存储进一个集合当中
            vec.push_back(sub);
            return;
        }
        for (int i = start; i < S.size(); ++i) {//存储的顺序
            sub.push_back(S[i]);
            subset(S, vec, sub, i+1, k);
            sub.pop_back();
        }
    }
};

解法二：

思路分析：同样也可以使用递归遍历的方法进行判断，每个元素只有两种状态，选择或者不选择，选择当前第i个元素，计算出其的所有组合结果，或者是不选择该元素，返回其组合的结果值。还是首先把集合内的元素进行排序，添加一个空子集，随后进行判断。

具体java代码为：

import java.util.*;
 
public class Solution {
    public ArrayList subsets(int[] S) {
        Arrays.sort(S);//升序排列
        ArrayList res = new ArrayList();
        ArrayList sub = new ArrayList();
        res.add(sub);//空子集添加
        for(int i = 0 ; i< S.length; i++){ //选择了第i个后，将sub增加一个S[i] ArrayList newres = new ArrayList();//重新创建一个保存对象
            for(ArrayListlast : res){
                ArrayList newres1 =  new ArrayList();
                newres1.addAll(last);//将last中的所有元素添加到newres1中
                newres1.add(S[i]);//改变newres1的值，然后保存
                newres.add(newres1);
            }
            res.addAll(newres);//将最终值添加到res中
        }
        return res;
    }
}

设定了两层for循环，故时间复杂度为O(N^2)，空间复杂度为O(N)。