DFS notes

update Jan 7, 2018 16:05

Basic Idea

DFS 是一种搜索算法，一个非常好的应用是用来解决排列组合问题。

写 DFS 的时候要注意两个要点：

1. What does it store on each level, 每层的意义以及总的递归深度；

2. How many different states should we try to put on each level，即每层有多少个不同的分支需要继续；

经典题目：

1. Subsets of a set

按照之前的两点考虑，例如输入是一个包含三个元素的set：{'a', 'b', 'c'}， 则：

• 一共有三层 dfs，每层考虑该位置的元素是否包含；

• 每层有两个分支，即包含或者不包含；

时间复杂度 为 O(2 * 2^n) = O(2^n), 因为一共有 n 层，每层每次拓展出 2 个分支， 即这种方法所搜索的隐式图中共有 2 * 2^n 个节点；

以上的两种情况可以由如下方式来表示：

    'a'  'b'  'c'
     0    0    0
     1    1    1

即有三层dfs，分别对应 'a', 'b', 'c'，每层中又有两个分支，分别对应 0, 1 即包含或者不包含当前字符。

于是，根据之前的表示法，我们可以对有重复元素的 input set 进行表示, 例如input：{'a', 'b', 'b', 'b', 'c'}：

     'a' 'b' 'c'
      0   0   0
      1   1   1
          2
          3

即对于 'b' 来说，有四个分支，分别对应不选择 'b'，选第一个，第二个和选第三个；

讨论另一种思路：

个人认为还有另一种思路，在这种思路中，每一层代表在尚未考察过的元素中选择一个元素（或者一个都不选），而每一层的分支个数为剩余的尚未考虑过的元素个数加一（因为可能不选）。recursion tree 如下图：

    input: {1,1,2}

                                     {}(1,1,2)
                    /            -------|---------     \            \
                 {1}(1,2)        |    {1}(2)     |     {2}()        {}()
            /       |      \     |    /     \    | 
    {1,1}(2)      {1,2}()  {1}() | {1,2}()  {1}()|
    /     \                      ----------------- 这一支可以剪掉
{1,1,2}() {1,1}()                                 结果必然重复 

 每次进入下层递归会先check当前路径，这个操作相当于是在该层一个数字都不选，即为上图中每层的空元素。

时间复杂度分析： 这种思路时间复杂度就是 O(2^n)，因为这种方法所搜索的隐式图中只有 2^n 个节点，比之前一种要快。

但是这种思路和之前的那种相比，并没有实质性的优化，个人认为两者没有太大区别。但是在做 CombinationSum II的时候，我发现这种方法在去重的时候更加容易。如果用之前那种每层代表一个元素是否选取的方法，去重就很不方便。但是用这种方法，我们只需要保证每层中都只选择一组重复元素中的第一位就可以了。（CombinationSum II 的笔记）

update Jun 25, 2021 新的思路解释

可以把这种解法理解为第一层生成所有长度为1的subsets，第二层生成所有长度为2的subsets，以此类推。

2. Find all valid permutations using the parentheses provided

对于这道题，相当于在每次dfs之前需要加入判断，加右括号之前需要判断是否有与之对应的左括号。从 recursion tree 的角度上看，相当于对 recursion tree 进行 pruning：

                              ""  _________
                          /       | \     |
                        /         |   \   |  因为没有与之相配的 “（”，这部分被 prunning
                      "("         |   ")" |
                   /       \      --------- 
                  /          \
                "(("         "()"_______
                /   \       /   | \    |
            "((("  "(()"  "()(" | "())"| 被剪枝
                                --------
                    ...

至于其与上面 subsets 的区别就是这道题目每次进入下层dfs之前需要做额外判断。 时间复杂度 为： O(2^2n), n 为括号的对数。

3. Print all combinations of coins that can sum up to a total value k

例如，对于 input：{1，5，10，25}，要求得到所有 sum 为 99 的组合。

思路 1：（bad idea） 每层有四个分支，分别表示该层使用第几个数，层数则为 targetSum / min{input} 层。这种方法之所以不好，是因为递归深度和 input 的 targetSum 有关，如果 sum 很大，递归会非常深。同时，因为递归深度深，以前面的输入为例子，时间复杂度可能为 O(4^99), 是很慢的。

思路 2： 层数只有 4 层，每层中分别考虑一个数字选取的次数，即每层有 remainingSum / currNumber 个分支。这种方法递归深度浅，比较好。时间复杂度的话，考虑最多的分支99（在选取 1 的那层有99个分支），时间复杂度为 O(99^4), 远远好于 思路 1；

思路 2 如下图所示：

      1         5         10         25
    ------------------------------------
      0         0         0         0
      1         1         1         1
      2         2         2         ...
      3         3         3
      ...      ...        ...
      99

图中所示，一共有四层，每层的分支数各不相同，依照剩余的 remainingSum 和当前数字的大小而定，但最多为 99。

4. Permutations

首先思考每层代表什么，一共有多少层。在这道题目的情况下，例如input为 {1,2,3}，则 dfs 共有 3 层，每层代表一个位置（0，1，2）。每层的分支数量为当前剩余候选数字的个数。recursion 如下图所示：

    input：(1,2,3)
                          {}(1,2,3)
                        /    |     \
                     /       |        \      
                  /          |           \
L1:       {1}(2,3)        {2}(1,3)       {3}(1,2)
         /  \             /   \            /   \   
        /    \           /     \          /      \
L2:  {1,2}(3) {1,3}(2) {2,1}(3)  {2,3}(1) {3,1}(2) {3,2}(1)
       |        |        |          |        |         |
L3:   123     132       213        231      312       321

实现技巧： 不再像之前那样使用一个selected数组，每次循环遍历，而是采用一种每次 swap 当前选择元素到最前面的方法，这样做可以很大程度上提高时间复杂度以及空间复杂度。

这种方法叫做SWAP-SWAP。当需要仅改变元素顺序找各种permutation时，首选这种方法。

框架如下：

# list<char> input, int pos
def dfs(input, pos):
    if pos == len(input):
        # store this input as a result
        return
    for i in range(pos, len(input)):
        swap(input, pos, i) # 将选定的换到第pos位
        dfs(input, pos + 1) # 向后进行，因为第pos位已经确定
        swap(input, pos, i) # back tracking

时间复杂度： O(n!)

Follow up：为什么不用BFS来做permutation问题？

答：因为如果用BFS的话，queue.size 会指数型增长，空间复杂度太高。