什么时候会用到 DFS？
做算法题时，一旦遇到'输出所有方案'、'枚举所有排列组合'这类需求，深度优先搜索（DFS）往往是最直接的解法。它穷举所有可能性，通过递归一层层往下试探，走到死胡同再回退尝试别的分支。
DFS 的核心思想
DFS 全称 Depth First Search，可以理解为'一条路走到黑'。借助递归，每一步的选择构成一个状态，直到满足终止条件（比如凑齐了要求的分量），记录答案并回溯；如果不满足，就剪枝回头。
和分治有点像，但分治通常是分解问题再合并，DFS 更偏重枚举所有路径。写 DFS 最怕两个东西：递归爆栈和重复计算，不过对于大多数练习题，控制好分支就够了。
怎么把 DFS 写成代码
写一个 dfs() 之前，我会先想清楚三样东西：
- 状态：哪些参数能唯一描述当前这一步？
- 边界：到哪一步必须停，并判断是否有效？
- 初始调用：从什么状态启动递归？
把这三个定下来，框架就出来了。下面用一个具体题目演示。
例题：正整数分解
把正整数 n 拆成 m 个正整数，要求后面的数大于等于前面的数，输出所有方案。
如果不确定 m，用多重循环就没办法，DFS 正合适。
状态设计
对于这个题，我需要的状态是：
remain：还剩多少可分配last：上一个选的数，保证当前选的数 >= lastdepth：已经分出了几个数
函数原型可以是 void dfs(int remain, int last, int depth)。
递归边界
当 depth == m 时，检查 remain 是否为 0。是，就输出一组解；不是，直接返回。
递归过程
从 i = last 开始循环，到 i <= remain。如果选了 i，传下去变成 dfs(remain - i, i, depth + 1)。注意如果 i > remain，直接 break。
主函数
读入 n 和 m，调用 dfs(n, 1, 0)（如果要求正整数分解，last 最小可以是 1）。
思路流程
dfs(remain, last, depth):
if depth == m:
if remain == 0: 输出
return
for i = last to remain:
dfs(remain - i, i, depth + 1)
这个框架处理了所有合法分解，而且天然保证了顺序。
小结
DFS 没有固定模板，不同题目状态定义出入很大。但核心总是'定义状态 → 设置边界 → 从初始状态开始搜索'。多写几道题，自然能摸清门道。
