# DFS

1 Basic

* 深度优先搜索（Depth-first Search）中，90%的问题，不是求组合（Combination）就是求排列（Permutation）
* 组合问题可以参考全子集问题，排列问题可以参考全排列问题
* Backtracking是DFS中一个非常重要的部分，经典题目需要非常熟练掌握
* DFS经常需要进行Deep Copy来传入搜索的结果
* 利用DFS进行暴力枚举也是一种常见的情况
* 通常结果数目就是时间复杂度

2 Search/Traverse

* DFS更多的还是作为搜索算法，可以递归的进行遍历，没有返回值
* 或者作为某些条件下的遍历
* 也可以在递归的时候进行分治算法，有返回值，如果有重复子问题或者优化结构，可以引入memo表

3 Memo

* 一个很重要的内容是记忆化，可以延伸至Top-Bottom的动态规划的一类问题

4 Path

* 最短路径
* 指定路径
* 图相关问题