手把手学会DFS （递归入门）

目录

算法介绍

递归实现指数型枚举

递归实现排列型枚举

递归实现组合型枚举

---

算法介绍

🧩DFS 即 Depth First Search ，中文又叫深度优先搜索，是一种沿着树的深度对其进行遍历，直到尽头之后再进行回溯，再走其他路线的方法，在对数据进行枚举，或求子串数量时具有奇效。该算法的实现取决于递归，因此如何设置递归的结束条件，以及什么时候调用递归便显得十分重要。

🧩通过 DFS 进行遍历，便可以无遗漏地走遍整个树，再根据题目要求在特定的位置对数据进行处理或输出。

🧩最重要的一点便是，当我们一条路走到底之后，就要回溯，就像上图中 3 5 6 步那样回到上一个节点。之后会判断是走另外一条路还是再回溯到上一层，由于在回溯前我们就已经对数据进行了处理，所以要对数据进行还原，即回溯到第一次到达这个节点时的那份数据。具体的细节就留到题目里面讲吧。

递归实现指数型枚举

传送门：AcWing 92. 递归实现指数型枚举

🧩DFS 的入门题，要求在 1~n 之间找所有可能出现的子序列的情况。可以全选也可以全部都不选，但输出的方式就比较宽松不需要特别处理。

🧩于是我们就可以将 1~n 的每一位都看作有两个选择，选和不选，用一个数组存储。每次到达叶节点的时候便完成一次枚举，并输出。而每次递归参数就加一，表示往下一层，位数的增加。注意的细节都写在代码里了，结合代码进行理解。

如果比较难想象一定要画递归图！！！！

#include
#include
#include
#include
using namespace std;
const int N = 15;
int n;
int sta[N];  //状态数组，表示当前位的数选或不选
void dfs(int i)
{
    if(i == n)  //位数等于n，表示所有数的状态都已确定，可以进行输出
    {
        for(int j = 1;jn)  //从1开始递归则判断条件为i>n从0开始则是i=n结束递归
    {
        for(int j = 1;j