题解 | #集合的所有子集(一)#

题目主要信息:

• 给定一个没有重复元素的数组看成集合，需要给出该集合的所有子集
• 给定的集合原本是升序，子集元素须按照升序排列

具体思路:

根据数学知识，我们可以知道$nn$个元素的集合加上空集和本身一共有$2^{n}2^n$个子集，那么可以一一枚举构造，需要做个$nn$到$2^{n}2^n$的映射。

• step 1：用二进制的形式刚好可以实现$nn$到$2^{n}2^n$的映射，设置一个掩码mask，从$00$到$2^n-12^n-1$。
• step 2：对于每个mask值都遍历一次数组，每次遍历的时候将数组下标与掩码相应的位进行比较，如果掩码该位取1，则本次子集可以取这个元素，这样根据二进制数字的特点刚好可以取完$2^{n}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\ast 2^n)O(n*2^n)$，一共需要构造$2^{n}2^n$个子集，每次构造都需要遍历原数组一次
• 空间复杂度：$O(n)O(n)$，记录每个子集的临时数组最长为$nn$，res属于返回必要空间，不属于额外空间