1. 每一层代表什么含义
搜索到当前层时所有可能的解(孙老师授课时对这个问题描述得更深刻,我没有完全理解)
2. 每层有多少个状态需要尝试
对于subsets有两个状态:加 或 不加 当前元素
代码比解法一简单很多:
解法三、对解法二树结构的不同看法
在得到DFS Recursion tree之后,我每次都是从leaf node取值。那么从树结构的中间取值可不可以?答案是可以的。
观察发现,每次都取左节点的值(包括root),可以得到同样的结果。或者换一种角度看,因为所有的右leaf节点都可以有多个父节点与之对应,而与之对应的父节点肯定不是leaf节点。再观察发现这些多个节点中只有一个左节点。并且,除了左leaf节点外,其余的左节点都有恰好对应一个右leaf节点。需要多引入一个 boolean on Left 的变量来判断。这里并不能完全省略所有的右节点,因为右节点帮助我们再生成下一层的左节点。
解法四、另一种DFS
这也是另一种常见的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大的所有选择。