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

NC27 集合的所有子集

题意分析：

枚举出某个没有重复集合的所有子集，并且有序。

题解一（回溯）：

含有n个元素的集合，其子集一共有 $2^n$ 个。创建函 $backtrack(vector<vector<int>>\&ret,vector<int>nums,int\ index,vector<int>tmp)$ ；

ret存放最后的结果，nums是提供的集合，index表示从nums的什么位置开始选取元素，tmp存放每次生成的子集。

开始有backtrack(ret,nums,0,tmp)。当nums位置0处的元素被选定了以后，我们就下一步就是选取位置1处的元素。backtrace结束后，选定的元素要删除。

值得注意的是：所提供的nums一定要有序，这样我们生成的最后结果也是有序的。如果不是有序的，最后我们还需要sort一下。

vector<vector<int>> subsets(vector<int>& nums) {
        //调用backtrace生成子集
        vector<vector<int>>ret;
        vector<int>tmp;
        backtrack(ret,nums,0,tmp);
        return ret;
    }
    void backtrack(vector<vector<int>>&ret,vector<int>nums,int index,vector<int>tmp){
        //初始tmp为nums的一个子集，加入到最后结果中
        ret.push_back(tmp);
        for(int i=index;i<nums.size();i++){
            //生成下一步要添加子集
            tmp.push_back(nums[i]);
             //开始回溯
            backtrack(ret,nums,i+1,tmp);
            //回溯结束后剔除掉加入的元素
            tmp.pop_back();
        }
    }

时间复杂度： $O(2^n)$ ，n为所提供的集合大小。

空间复杂度： $O(n)$ ，回溯最多深度为n.

题解二（迭代法）：

假设原集合中元素个数为n，原有集合中每一个元素有两种状态加入到子集中，加入或者不加入。 $2^n$ 个子集正好和二进制 $0->2^n-1$ 这 $2^n$ 个数的二进制位对应。假设在 $0->2^n-1$ 中某个数字位a，我们只要把a的二进制位上的1所在的位置，对应原集合中的数，加入到子集中即可。
图片说明
举个例子,当N==2时候，我们遍历从0到 $2^2-1=3$ ,枚举每个数的二进制展开，
对于0，我们什么也不取，作为子集
对于1，我们取数组第一个数作为子集
对于2，我们取数组第二个数作为子集
对于3，我们组数组第一个，第二个数作子集

vector<vector<int>> subsets(vector<int> &nums) {
    int n = nums.size();
    vector<int> tmp;
    vector<vector<int>> ret;
    for (int i = 0; i < (1 << n); i++) {
        tmp.clear();
        for (int j = 0; j < n; j++) {
            //将数字i进行二进制展开，然后添加指定位置的元素
            if (i & (1 << j)) {
                tmp.push_back(nums[j]);
            }
        }
        //添加完毕后，加入到结果中
        ret.push_back(tmp);
    }
    return ret;
}

时间复杂度： $O(n2^n)$ 。我们从0遍历到 $2^n-1$ ，并且对每一个数做了一次二进制展开。

空间复杂度： $O(n)$ 。我们需要额外的vector存放生成的子集。