目录
算法介绍
🧩DFS 即 Depth First Search ，中文又叫深度优先搜索，是一种沿着树的深度对其进行遍历，直到尽头之后再进行回溯，再走其他路线的方法，在对数据进行枚举，或求子串数量时具有奇效。该算法的实现取决于递归，因此如何设置递归的结束条件，以及什么时候调用递归便显得十分重要。
编辑
🧩通过 DFS 进行遍历，便可以无遗漏地走遍整个树，再根据题目要求在特定的位置对数据进行处理或输出。
🧩最重要的一点便是，当我们一条路走到底之后，就要回溯，就像上图中 3 5 6 步那样回到上一个节点。之后会判断是走另外一条路还是再回溯到上一层，由于在回溯前我们就已经对数据进行了处理，所以要对数据进行还原，即回溯到第一次到达这个节点时的那份数据。具体的细节就留到题目里面讲吧。
递归实现指数型枚举
编辑
🧩DFS 的入门题，要求在 1~n 之间找所有可能出现的子序列的情况。可以全选也可以全部都不选，但输出的方式就比较宽松不需要特别处理。
🧩于是我们就可以将 1~n 的每一位都看作有两个选择，选和不选，用一个数组存储。每次到达叶节点的时候便完成一次枚举，并输出。而每次递归参数就加一，表示往下一层，位数的增加。注意的细节都写在代码里了，结合代码进行理解。
如果比较难想象一定要画递归图！！！！
编辑
#include<cstdio> #include<string> #include<iostream> #include<algorithm> using namespace std; const int N = 15; int n; int sta[N]; //状态数组，表示当前位的数选或不选 void dfs(int i) { if(i == n) //位数等于n，表示所有数的状态都已确定，可以进行输出 { for(int j = 1;j<=n;j++) { if(sta[j] == 1) { printf("%d ",j); } } puts(""); return; } sta[i+1] = 1; //1表示选该数字 dfs(i+1); //往下一层递归 sta[i+1] = 0; //回溯后重置，但其实下面就会覆盖掉加不加没区别，只是为了好理解 sta[i+1] = 2; //2表示不选 dfs(i+1); sta[i+1] = 0; } int main() { scanf("%d",&n); dfs(0); //从第0层开始 return 0; }
递归实现排列型枚举
🧩传送门：AcWing 94. 递归实现排列型枚举
编辑
🧩依题意，一个 1~n 的整数要输出其所有的排列情况，这便于上一题不同了，上一题是每位数的相对位置都是固定的，输出长度是不固定的。但这题固定长度，但每个位的数字并不是固定的。那我们便可以从每位出发，枚举每一位可能出现的数字，但每个数字都只能出现一次。因此需要一个数组记录这个数字是否被使用过。递归结束时输出当前方案，再进行回溯。
#include<cstdio> #include<string> #include<iostream> #include<algorithm> using namespace std; const int N = 10; int n,count; int sta[N]; //用于存储方案 bool used[N]; //有没有被用过 void dfs(int i) { if(i>n) //从1开始递归则判断条件为i>n从0开始则是i=n结束递归 { for(int j = 1;j<=n;j++) printf("%d ",sta[j]); //输出 puts(""); return; } for(int j = 1;j<=n;j++) //寻找还没有用过的数 { if(!used[j]) //true表示用过，false表示未用 { sta[i] = j; //i位置选j used[j] = true; //标记j已使用 dfs(i+1); //往下一位递归 used[j] = false; //回溯后当前位就不使用了于是置为false } } //之后继续寻找下一个没有用过的数 } int main() { scanf("%d",&n); dfs(1); return 0; }
递归实现组合型枚举
🧩传送门：AcWing 93. 递归实现组合型枚举
编辑
🧩这题就有点像上面两题的结合版，给定 1~n 的范围输出指定长度的从小到大的全部排列。要注意的是输出的情况是严格递增的，即不会出现中途有数字小于前面数字的情况。所以在查找没用过的数字时，需要从上一位加一开始查找。只有位数达到标准了才输出，因此会筛选掉一些不符合要求的答案。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N = 26; int n, m; int sta[N]; //用于存储方案 bool used[N]; //有没有被用过 void dfs(int x) { if (x > m) //位数符合，可以输出 { for (int i = 1; i <= m; i++) { printf("%d ", sta[i]); } printf("\n"); return; } for (int i = sta[x - 1] + 1; i <= n; i++) //由于输出是严格递增的由此当前位一定比上一位大 { if (!used[i]) //当前数未被用则进行操作，否则跳过 { sta[x] = i; //当前位置选i used[i] = true; //标记当前位置已使用 dfs(x + 1); //向下递归 used[i] = false; //状态回溯 } } //之后继续寻找下一个没有用过的数 } int main() { scanf("%d%d", &n, &m); dfs(1); return 0; }
🧩好了这次DFS的入门讲解到这里就结束了，如果对你有用的话还请留下你的三连加关注。算法的学习还是建立在多练习上，学会了思想还需要多多实践才能熟练地掌握。
