Subsets

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

Note:The solution set must not contain duplicate subsets.

For example,
If nums=[1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

思路分析

第一眼看到这道题就会感觉要穷举所nums数组中所有的数才能够得到子数组，然后加上题目中又要求return all posible subsets, 基本可以判断这道题会用到DFS，这是做这道题的初步的思路分析

然后关联第二类题型的template来实现，在python实现的时候，同一种template有两种实现方式

第一种实现方式是用一个临时数组来存放每一个subset，这样的话每一次调用递归后这个临时数组的内容就会发生变化（用append来实现添加新的element），因为数组在每一次递归的时候变化了，所以每次递归调用结束后还要把最后的一个元素pop出来进行回溯。另外将临时数组中存放的subset 添加到最终结果subsets数组时要生成新的对象（python中用'[ ]+'来实现），否则最终返回的结果将随着临时数组subset的变化而变化了。

第二种实现方式是用path路径的方式来实现，每次把新的遍历到的节点添加的path数组中。path也是一个list，但是它与subset的区别是什么呢？subset在每次递归的时候内容发生了变化（把新遍历到的节点append进list中了），而path在每次递归的时候内容没有发生变化。所以使用path路径的方式来实现时就不需要通过pop的方式来进行回溯了，那既然DFS是需要回溯的，path方式是怎样实现回溯的呢？答案是通过递归的方式，因为递归本身在走到path终点的时候就会回到来时的路

• 通过临时数组subset的方式来实现

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        self.dfs(sorted(nums), 0, [], res)
        return res

    def dfs(self, nums, index, subset, res):
        res.append([]+subset)
        for i in xrange(index, len(nums)):
            subset.append(nums[i])
            self.dfs(nums, i+1, subset, res)
            subset.pop()

• 通过path路径的方式来实现

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        self.dfs(nums, 0, [], res)
        return res

    def dfs(self, nums, index, path, res):
        res.append(path)
        for i in xrange(index, len(nums)):
            self.dfs(nums, i+1, path+[nums[i]], res)

源码分析

两种实现方式都是用DFS + 递归的方式来实现的，所使用的模版也是一样的。主要的区别是对数组的操作的不同。

既然是递归实现，那就要满足递归三要素，其中一个要素就是要有退出条件，即当递归到达某一种情况时不需要调用递归函数而直接可以得到解。乍一看这两种实现方式都没有一个显式的退出条件（if <> : return），但是仔细分析可以看出for循环在控制着递归函数调用的次数（不是无限循环），也就是说退出条件隐式在for循环中。

回溯法可以用图示和函数运行的堆栈图来理解，一般使用图形和递归的思想进行分析。下面以数组[1,2,3]为例来分析上面两种实现方式的图形递归堆栈图：

• 通过临时数组subset的方式来实现

下图所示为subset和result随着栈的动态变化过程，箭头向下表示subset.append和result.append操作（进栈），箭头向上表示subset.pop （回溯／出栈）操作

• 通过path路径的方式来实现

下图所示为subset和result随着栈的动态变化过程，箭头向下表示path数组的变化和result.append操作（进栈），箭头向上表示递归出栈过程

复杂度分析

时间复杂度

通过DFS递归实现的时间复杂度公式为：O(构造解的复杂度 * 解的个数)。每次递归里面有个for循环，所以每次构造解需要O(n)时间，那么总共有多少的解呢，2^n个，所以可以计算出总的时间复杂度为O(n*2^n)

空间复杂度

空间复杂度跟解的个数（递归调用的个数）是一直的，所以是O(2^n)