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

思路：

题目的主要信息：

有一个没有重复元素的整数集合S，经测试S的元素本就是升序
求所有子集，子集顺序不定，子集中无重复内容，但是子集中的元素必须是升序

方法一：穷举法
具体做法：
学过离散数学就知道，如果集合的元素是 $n$ 个，那就有 $2^n$ 个子集，如果我们枚举一一构造，那就需要做一个 $n$ 到 $2^n$ 的映射，我们可以想到二进制数就是一个这样的一一映射。因此，我们可以设置一个掩码mask，从 $0$ 到 $2^n - 1$ ，遍历数组的时候，我们可以将下标与掩码的位进行比较，只取位为1时的下标，这样就可以刚好取到 $2^n$ 个子集，且不会有重复。
因为构造时是从首位开始与掩码比较，因此子集内部是递增序列。
图片说明

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<int> s;
        vector<vector<int>> res;
        int n = S.size();
        for (int mask = 0; mask < (1 << n); mask++) { //遍历2^n个
            s.clear(); //每次需要清空缓存数组 
            for (int i = 0; i < n; ++i) {
               if (mask & (1 << i)) {   //将与掩码匹配的加入
                    s.push_back(S[i]);
               }
            }
            res.push_back(s);
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n*2^n)$ ，一共要构造 $2^n$ 个子集，每次构造为一次遍历 $O(n)$
空间复杂度： $O(n)$ ，临时变量s作缓存构造每个子集，其中res是返回必要空间，不算额外空间

方法二：递归+回溯
具体做法：
我们都知道数组的所有子集，如果一个子集选取了0，那么子集组合的可能性就变成了1到n-1的组合，这俨然变成了一个递归可以解决的子问题。因此我们可以遍历数组，首先加入当前遍历的下标，对于后续的组合就将其后面的部分看成是一个子问题递归解决。
值得注意的是，递归结束我们要删除尾元素来回溯，回到子问题的父问题。
图片说明

class Solution {
public:
    void backtrack(int i, vector<int>& S, vector<vector<int> >& res, vector<int>& temp) {
        res.push_back(temp);
        for(int j = i; j < S.size(); j++) {
            temp.push_back(S[j]);
            backtrack(j + 1, S, res, temp);  //从下一个下标开始继续递归
            temp.erase(temp.end() - 1); //删除尾部，回溯
        }
    }
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int>> res;
        vector<int> s;
        backtrack(0, S, res, s);//从0开始，空数组入递归
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n*2^n)$ ，遍历数组所有元素为 $O(n)$ ，树型递归为 $O(2^n)$ ，删除尾元素为 $O(1)$
空间复杂度： $O(n)$ ，递归栈深度及辅助数组temp