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

  • Note: The solution set must not contain duplicate subsets.

  • 我假设给的input nums[] 都是已经sort好的

For example,

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

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

解法一、pure recursion (bottom up)

由要解决的problem的定义出发,尝试划分成相同problem的子问题,并且利用子问题的结果来解决原来的问题,而最关键的点有两处:base caseinduction rule

base case代表的是最小号的不可分的问题,induction rule表示的是如何利用子问题的结果。比如,我们要找 'abc' 的所有subsets,我们可以尝试先划分子问题找到induction rule:先找到“bc”组成的所有subsets {'', 'b', 'c, 'bc'},由'abc'组成的所有subsets包含两类:1)包含'a'的subsets 和2)不包含'a'的subsets。

我们可以看到2)就是子问题'bc'的结果,而1)可以由2)的每个subset加上元素'a'来组成,依次类推。而另一个关键点base case:最小的不可分割子问题,也就是''的所有的subsets,自然只包含一个元素''。针对原来的问题,将递归的过程从下往上表现出来如下所示,当递归深度是nums.length时,这个解法利用的是下一层recursion的结果来生成这一层的结果。

technical-008-1

technical-008-5

优点: 思路简单

缺点:在不需要返回所有的结果的时候比较浪费空间,因为当前层recursion必须要知道下一层的全部结果

优 化

计算机在进行递归的时候会有额外的栈上的空间开销,当递归层数很深的时候回有可能stackoverflow,这是一个我们需要注意和重视的情况。从上面的解法不难看出,我们可以比较容易的将它转化成Iterative的解法,从最小号的问题开始解决,利用相同的induction rule,这也是Dynamic Programming解法最根本的来源。

technical-008-6

解法二、DFS (top down)

根据孙老师的传授的要诀,用DFS基本方法解决问题时要明确两点:

1. 每一层代表什么含义

搜索到当前层时所有可能的解(孙老师授课时对这个问题描述得更深刻,我没有完全理解)

2. 每层有多少个状态需要尝试

对于subsets有两个状态:加 或 不加 当前元素

technical-008-6

代码比解法一简单很多:

technical-008-7

解法三、对解法二树结构的不同看法

在得到DFS Recursion tree之后,我每次都是从leaf node取值。那么从树结构的中间取值可不可以?答案是可以的。

technical-008-3

观察发现,每次都取左节点的值(包括root),可以得到同样的结果。或者换一种角度看,因为所有的右leaf节点都可以有多个父节点与之对应,而与之对应的父节点肯定不是leaf节点。再观察发现这些多个节点中只有一个左节点。并且,除了左leaf节点外,其余的左节点都有恰好对应一个右leaf节点。需要多引入一个 boolean on Left 的变量来判断。这里并不能完全省略所有的右节点,因为右节点帮助我们再生成下一层的左节点。

technical-008-8

解法四、另一种DFS

technical-008-4

这也是另一种常见的DFS思路,依然根据孙老师传授的要诀来解释这种思路:

1. 每一层代表什么含义:长度相等的所有可能性

2. 每层有多少个状态需要尝试:每一层新增的状态根据上一层来决定,如果上一层打印到了nums[st], 则这一层新增的状态是从 st + 1 到 nums.length - 1

划重点

这个思路用到的是另外一种构建subset的方法:'每个size为k的subset都是由一个size为k-1的subset加上一个元素得到的'。而我们在构建subset的过程当中要避免出现重复,比如:'123', '132', '213','231','312','321'这几个都是相同的subset,我们只应该让它在我们的构建方法中出现一次,否则会有重复。

常见的Intuition是“如果我们在构建subset的过程中保持一定的顺序,那么上述这些可能出现的subset只会出现其中的唯一一个!',那么我们可以选用的方法是,在构建subset的过程中,每次新添加的元素保持递增的顺序,这样'132','213'等等都不会出现在我们的结果里面,当我们已经有了一个size为1的subset '2',我们是不会再把“21”构建出来的,下一次新添加的元素只能是比2大的所有选择。

technical-008-9