子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解题思路：
最容易想到的就是排列组合的方法，把数组里的元素进行组合排列，选1个元素的有多少种，再选2个元素的有多少种，再选3个元素的...
但这样时间复杂度很高，要遍历很多次，代码写起来也难受（虽然我并没有写）。
那我们思考有没有其他思路，然后，emmm，没想到。。。
不过我们有度娘，找了一下，有个算法叫做深度优先算法，先看下面这张图片

image.png
我们在数学课上学过，一个长度为n的数组的幂集个数等于2的n次方。
以[1,2,3]为例，我们可以这样理解这个定理：
最开始是个空集，什么都没有，然后我们加了一个1进去，现在有两个子集：
[1]和[]
再加个2进去，然后是4个子集：
[1,2] [2] [1] []
可以发现，有一般是原来的子集，还有一般是在原来每个子集中都加了个2。
所以每多一个数，子集总数就翻倍，也就是2的n次方了。
按照这个思路，我们只需遍历数组nums,然后nums中的元素按上面的思路添加到结果集中就好了。
但编程方式有两种，一种是按照上面的流程写，每拿到一个新元素，在老集合的每次子集中添加新元素，还要保留本身老集合中的所有子集。
还有一种是按照先序遍历的方法，上面那张图就是一棵二叉数，获取叶子节点就行了。
第一种代码如下：

def subsets(nums):
    import copy
    res = [[]]
    for i in nums:
        t = copy.deepcopy(res)
        for j in res:
            j.append(i)
        res.extend(t)
    return res

上面就是按照翻倍的思路写的，速度比较慢了，因为用到了深复制。
然而大佬们四行就搞定了，速度还比我的快得多。

 results = [[]]
    for i in nums:
        results = results + [[i] + num for num in results]
    return results

这段代码一眼能看懂什么意思，但要我自己想可能就想不出来了，所以python还有很多地方需要学习和摸索啊。。
然后是使用二叉树的方法：

    def subsets(self, nums):
        self.results = []
        self.search(sorted(nums), [], 0)
        return self.results
    
    def search(self, nums, S, index):
        if index == len(nums):
            self.results.append(S)
            return
        
        self.search(nums, S + [nums[index]], index + 1)
        self.search(nums, S, index + 1)