深度优先搜索

我们把问题的状态空间看作成一颗搜索树，深度优先搜索（DFS）就是在这颗搜索树上深度优先遍历。

深度优先搜索与递归和栈密切相关，因为这两种算法都是自底向上的计算过程。

搜索问题没有模板，只有几种常见的类型，我们针对每道题目都需要考虑它的剪枝优化

分支

分支的前后顺序是有区别的：

• 影响函数递归边界的输出字典序
• 在树的前序、中序、后序遍历中会有体现。

恢复现场recover

递归N叉树，每个分支都要recover，不然可能会出现$Segmentation Fault$

剪枝

void dfs 和 bool dfs的剪枝对比

$C_n^m$只输出一种情况，就要用bool来剪枝

https://leetcode.cn/submissions/detail/405400164/

https://leetcode.cn/problems/circular-permutation-in-binary-representation/submissions/405399005/

记录问题

如果返回值记录不下来(需要记录多个值，比如一个数组)，就直接入参的引用来记录

最下策是采用全局变量来记录

优化搜索顺序

排除等效冗余

可行性剪枝

最优性剪枝