题意概述

• 给定一个没有重复元素的整数集合
• 要求给出它的所有子集，子集中的元素必须按升序排列

方法一：递归

思路与具体做法

• DFS(k,S) k表示当前位置，S是初始的集合
• 每遍历到一层k，对集合的当前位置的数S[k]都有选择和不选择两种
• 可分别选定该元素然后递归下一层，不选定该元素然后递归下一层
• 递归树可想象成一个根结点是空集，然后每层左子树表示选中当前层元素，右子树表示不选中当前层元素，n个元素共n层$2^{n}2^n$2n个结点的满二叉树

class Solution {
public:
	vector<vector<int> >ans;
	vector<int>t;
    static bool cmp(vector<int> &a,vector<int> &b){
		if(a.size()!=b.size())return a.size()<b.size();
        return 0;
	} 
	void DFS(int k,vector<int>&S){
		if(k==S.size()){//递归边界，决定完所有元素是否选取 
			ans.push_back(t);
			return;
		}
		t.push_back(S[k]);//选该元素 
		DFS(k+1,S);//递归下一层 
		t.pop_back();//不选该元素 
        DFS(k+1,S);//递归下一层 
	}
    vector<vector<int> > subsets(vector<int> &S) {
   		DFS(0,S);
        sort(ans.begin(),ans.end(),cmp);//升序排列
		return ans; 
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(2^n\right)O(2^n)$O(2n)，一共$2^{n}2^n$2n个状态
• 空间复杂度：$O\left(n\right)O(n)$O(n)，用到了长度为n的辅助数组$tt$t，递归也进行$nn$n层

方法二：位运算

思路与具体做法

• 将子集各个元素的选取映射为，0表示不选取，1表示选取
• 则各个子集就可以表示成一组01序列
• n个元素有$2^{n}2^n$2n个子集（包含空集），也即$2^{n}2^n$2n个01序列，可对应着从10进制的$00$0~$2^n-12^n-1$2n−1来表示

class Solution {
public:
    static bool cmp(vector<int> &a,vector<int> &b){
		if(a.size()!=b.size())return a.size()<b.size();
        return 0;
	} 
    vector<vector<int> > subsets(vector<int> &S) {
        int n=S.size();
   		vector<vector<int> >ans;
        for (int i=0;i<(1<<n);i++) {//枚举0~2^n-1的二进制序列数表示子集序列 
            vector<int>t;
            for (int j=0;j<n;j++) {//分别枚举n个元素 
                if(i&(1<<j)){//1<<j该元素在二进制序列中的对应位，和i表示的子集序列按位与 
                    t.push_back(S[j]);//该元素放入子集 
                }
            }
            ans.push_back(t);//子集加入ans集合 
        }
        sort(ans.begin(),ans.end(),cmp);//升序排列
        return ans;  
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O(n\ast 2^n)O(n*2^n)$O(n∗2n)，一共$2^{n}2^n$2n个状态，每种状态需要$O\left(n\right)O(n)$O(n)时间构建子集
• 空间复杂度：$O\left(n\right)O(n)$O(n)，用到了长度为$nn$n的辅助数组$tt$t