DFS经典问题解析

定义

Depth First Search (DFS): an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

要点：树或者图搜索算法，回溯之前沿着一个方向explore AFAP.

DFS可以用递归(recursive) 或者迭代的方式实现。recursive method的general 实现逻辑如下：

/***
input: 图和图中一个节点
output:  v可以达到的所有节点被labeled as discovered.
***/
void DFS(graph, v){
      label v as discovered
      for all directed edges from v to w in G.adjacentEdges(v) 
         if vertex w is not labeled as discovered:
               DFS(G,w)
}

时间复杂度为O(n). 空间复杂度为调用栈的深度worst case is O(|E|)。|E| 为edge的个数。

iterative 的实现方式如下, 空间复杂度worst-case同样为O(|E|):

void DFS-iterative(graph, v){
      let S be a stack
      S.push(v)
      whille(!S.isEmpty()){
             v = S.pop()
             label v as discovered
             for all edges from v to w in G.adjacentEdges(v){
                  S.push(w)
             }
      }
}

DFS的递归实现和迭代实现，在现实生活中都有应用，各有优缺点，取决于具体应用场景:

Recursive: 实现简单，容易理解，在调用栈层数不多（Java将每层的方法调用（frame）存在方法栈当中，而方法栈的内存远小于heap）的情况下，可以使用。但实际生产中，图大多比较庞大复杂，比如朋友圈，Google的网页，交通路线图等，我们通常避免使用递归调用，容易产生StackOverflow的问题。
Iterative: 使用stack数据结构（Java会将这个栈分配在heap中），保存回溯路径。相比于Recursive实现复杂些，不容易直接想到。在算法面试或者竞赛中，通常不会使用。

本文主要围绕DFS，来讲解四道经典的面试算法题，尽管Leetcode上有200多道DFS类相关的题型，但掌握了本文的四道算法题思路，解决其他问题基本上没啥问题。

Note: 不要将DFS的Iterative实现和BFS混淆，尽管两者都是非递归调用实现，但是explore图的方向不同，BFS讲究由里到外的"地毯式搜索"，而DFS则会沿着一条路径走到黑，然后回溯。

子集合问题

题目要求print给定集合所有的subset，比如given input = {1, 2, 3}，那么expected输出应该为{{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}。

解题思路：打印出给定集合的所有子集本质上是一道数学题，给定集合每个元素都是相互独立的，它可以出现或者不出现在子集中，那么现在有3个元素，最中就会有2^3 = 8 种组合。想清楚这点之后，接下来就可以考虑构建递归树，构建递归树之前呢，我们需要问自己两个问题：

递归树每层代表什么含义？
Ans: 每层树表示的含义是对于每个元素是选取还是不选取，那么递归树一共有3层
每层有多少状态？
Ans: 每层有两个状态（选择或者不选择），那么三层树，最终会有8个状态，总体的时间复杂度为(2^n)， n为input的size。

想清楚上面两个问题就可以画出如下的递归树

图中每个中间节点都是子集结果的临时状态，而所有的叶子节点就是给定集合的子集。

OK，搞定了递归树的问题，代码就很好写了，如下所示


    /**
     * @param set: 给定的输入集合[1, 2, 3]
     * @param level: 当前level层数，表示visit 第level个元素
     * @param temp:用于保存当前临时结果集合
     * @param result: 用于保存结果的集合
     */
void findSubset(int[] set, int level, List<Integer> temp, List<List<Integer>> result){
         //递归到最后一层叶子节点
         if(level == set.length){
                 //将临时结果保存到最终结果集中
                 result.add(new ArrayList(temp));
                 return;
          }
          //选择加入当前元素, 然后继续向下递归
          temp.add(set[level]);
          findSubset(set, level + 1, temp, result);
          //选择不加入当前元素，然后继续向下递归
          temp.removeLast();
          findSubset(set, level + 1, temp, result);
}

相似的题型包括LC494 Target Sum, LC491 Increasing Subsequences，

硬币组合问题

给定一组硬币，根据已有的25, 5, 1 美分的硬币，求出所有的硬币组合凑出给定的目标金额，比如40美分。其中每种硬币的个数不限。这类硬币组合问题在面试中可谓是老生常谈了，比如LC518, LC322，LC494等等。

如上题一样，首先来画递归树，两个问题

递归树每层代表什么含义？
Ans: 每层代表使用一种类型的硬币比如第一层只使用25美分的硬币，有三种类型的硬币，那么递归树就有三层
每层有多少状态？
Ans: 每层的状态个数取决于当前的硬币的类型，比如第一层目标金额为40，选择使用25美分的硬币，就有40/25 + 1 (选择0个25没分) = 2 种状态。递归树节点最多有40状态(选择40 个 1 美分的硬币，0 个25美分，0个5美分)，那么时间复杂度就为O(40^3)。

接下来的就是代码实现了

 /*** 
 * @param moneyLeft: 剩下钱的数量
 * @param level: 当前使用的硬币
 * @param coins: 硬币种类集合, 
 * @param sol: 硬币个数, sol[i]表示使用coins[i]的个数
 */
void findCombination(int moneyLeft, int level, int[] coins, int[] sol) {
     If (level == coins.length - 1){
        sol[level] = moneyLeft; //假设coins[3] = 1，这一点要和面试官确认
        print(coins, sol); //打印结果
        return
     }
    for (int i = 0; i * coins[level] <= moneyLeft; i++){
        sol[level] = i; //使用coins[level]的个数
        findCombination(moneyLeft -  i * coins[level] , level  + 1, coins, sol );
    }
}

private String print(int[] coins, int[] sol) {
     for(int i = 0; i < coins.length; i++){
          System.out.println("使用 {} 个 {} 美分硬币".format(sol[i], coins[i]));
     }
}

解决本题还有另外一种思路，给定三种硬币 25, 5, 1，那么递归树每一层其实有三种选择，要么选择1个25美分，要么选择1个5美分，再要么选择1个1美分，那么递归树就会有99层，每层有3个选择，时间复杂度则为O(3^99)。如果给定一个很大的目标金额，那么很容易出现StackOverflow。

排列问题

Print all valid permutations of ()()()

valid case: whenever we add (, it is always valid;

              Whenever we add ), we must guarantee number of the left parenthesis added so far > right parenthesis added so far.

What does it stores on each level ? (每层表什么含义)

Six levels, for each level, it makes the decision whether to put left or right parenthesis on each position.

How many different stages should we try to put on this level ? (每层有多少个状态)

两个状态. Add Left parenthesis or right parenthesis

[图片上传失败...(image-7c71eb-1573464603037)]

正在上传...[取消](javascript:void(0))

void DFS(int left, int right, String temp, List<String> result){

if (left == n && right == n){

                  result.add(temp.toString());

           }

           if (left < n){

              DFS(left + 1, right, temp + “(”,  result);

          }

          if(right < left){

                  DFS(left, right + 1, temp + “)”,  result);

           }

}

DFS绝大部分问题的解题思路是枚举出所有的组合，然后根据问题要求过滤出符合条件的答案。

补充说明

画递归树主要帮助我们分析时间复杂度。

Print all valid permutations of ()()() 左括号，右括号

凑硬币金额根据已有的 1, 5, 25分coin，打印出所有的组合，99金币

Given a String, and output all permutation ------->switch 来, switch去

Permutation of a String with (without) duplication

Permutation of all subsequences of a sorted string (allow a set contains duplicate string)

Permutation of factors of number

Levels

生成随机的maze

重建行程单，给定一组行程列表 list of <start, end>，求访问node的顺序，如果多个path 存在，取lexical order 较小的那个

Tree的Traversal, pre-order, in-order and post-order

例题4. Given a String, and output all permutation

For example, s = “abc”

DFS基本分析法

What does it stores on each level ? (每层表什么含义)

3, each level represents each position, the character we can choose

How many different stages should we try to put on this level ? (每层有多少个状态)

第一个postion, we have 3 choice, 第二个postion, we have 2 choice, 第三个只有一个

时间复杂度取决于数最后一层节点的个数O(n!)

[图片上传失败...(image-745401-1573464603037)]