leetcode Subsets - c++编程基础

题目：

Given a set of distinct integers, S, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:
```
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
```
那么有几种情况呢，如果给你的数字长度为n的话，那么首先是空数组1；选一个呢，为n个；如此下去，一个的个数为2^n个子数组。

这里给出一个java代码：
```
import java.util.*;

public class Solution {
    public List
    
     > subsets(int[] S) {
        int totalLength  = 1<
     
      > l = new ArrayList
      
       >(); Arrays.sort(S);//数组进行排序 for (int i=0;i
       
         tmp = new ArrayList
        
         (); for(int j=0;j
         
          > j) & 1 )!= 0){ //将s[n]分别用二进制的n-1位代替 tmp.add(S[j]); } } l.add(tmp); } return l; } //测试主函数 public static void main(String[] args) { int[] array = {1,2,3}; Solution s = new Solution(); System.out.println(s.subsets(array)); } }
         
        
       
      
     
    
```
可能一下在看不懂上面的代码，特别是下面这段代码的意思。
```
 if(((i >> j) & 1 )!= 0)
```
看一个图，如下

上图中以S=[1 2 3 4]为例子，可以看到一个规律，就是在前面所有的subset的最后再添加一个位数，就成了新生成的subset。<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+u/LV36OsztLDx7zytaW1xNK7wO294s6qo6xzWzBdtPrC67b+vLbWxsr919bX7rrz0rvOu86qMaOsc1sxXbT6wuu2/r341sbK/dfWtbnK/bXatv7Ou86qMaOsyOe0y8/CyKWhozwvcD4KPHA+yOfJz8281tCjrLW5yv212rb+uPZzdWJzZXTOqlsyIDMgNF2jrMTHw7TV4rT6se3Xxcbk08O2/ry21sax7cq+zqoxMTEwID0gMTQg1eK6w8rHxuTN4s6nyv3X6bXEz8Kx6qOs1eLR+bK7xNzA7b3iyc/D5sHQs/a1xMTHuPa2zrT6wuvBy6Oou/LV38jnz8KjqTwvcD4KPHA+PC9wPgo8cHJlIGNsYXNzPQ=="brush:java;"> if(((i >> j) & 1 )!= 0)

由上面图中的原理，这样就比较好的理解下面的python代码了：
```
def subset1(S):
    A=[[]]
    S.sort()

    for n in S:
        for i in range(len(A)):
            ss = A[i][:] 
            ss.append(n) 
            A.append(ss)
    return A
```
下面的python在原理上再效率上会有所提高：
```
def subset2(S):
    res = [[]]
    S.sort()

    for n in S:
        res = res + [x + [n] for x in res]

    return res
```