9.4 编写一个方法，返回某集合的所有子集。

类似leetcode：

解法：

解决这个问题之前，我们先要对时间和空间复杂度有个合理的评估。一个集合会有多少子集？我们可以这么计算，生成了一个子集时，每个元素都可以“选择”在或者不在这个子集中。也就是说，第一个元素有两个选择：它要么在集合中，要么不在集合中。同样，第二个元素也有两个选择，以此类推，2相乘n次等于2^n个子集。因此，在时间和空间复杂度上，我们不可能做得比O(2^n)更好。

解法一：递归

首先将空集合加入，则当前集合为{

{}}

然后将第一个元素加入当前集合的每一个子集中，并将的到的新的子集也加入到当前集合中，则有{

{}{1}}

加入第二个元素时，则有{

{}{1}{2}{1,2}}

加入第三个元素时，则有{

{}{1}{2}{1,2}{3}{1,3}{2,3}{1,2,3}}

 

根据上面的思路，代码实现如下：

#include
     
      #include
      
       using namespace std;vector
       
        
          > subset(vector
         
           &S){    vector
          
           
             > ret; if(S.empty()) return ret; int n=S.size(); int i,j; ret.push_back(vector
            
             ()); for(i=0;i
             

tmp=ret[j]; tmp.push_back(S[i]); ret.push_back(tmp); } } return ret;}int main(){ vector

res={ 1,2,3}; vector

> ret=subset(res); for(auto a:ret) { for(auto t:a) cout<

<<" "; cout<