【AcWing】蓝桥杯备赛-深度优先搜索-dfs（2）
目录
写在前面：
读题：
输入格式：
输出格式：
数据范围：
输入样例：
输出样例：
解题思路：
代码：
AC ！！！！！！！！！！
写在最后：
写在前面：
距离蓝桥杯已经不足一个月了，
根据江湖上的传言，
蓝桥杯最喜欢考的是深度优先搜索和动态规划，
所以蓝桥杯也叫暴搜杯、dp杯，
那我备赛当然也就从深度优先搜索，也就是所谓的dfs开始。
题目：94. 递归实现排列型枚举 - AcWing题库
读题：
输入格式：
一个整数 n。
输出格式：
按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
数据范围：
1 ≤ n ≤ 9
输入样例：
3输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1解题思路：
这道题是深度优先搜索的经典题目，
我们使用深度优先搜索的时候，
第一个要注意的点是，我们要保证，
我们写出的递归结构能够遍历所有情况，
在我们初学搜索的时候，我们一定要画一个递归搜索树观察，
递归非常抽象，画图能很好的帮助我们解题。（以上递归搜索的基本思路，多熟悉总是好的）
接下来是具体思路：
根据题目说的从小到大输出每个方案，
字典序小的数放在前面，
我们画一个递归搜索树观察：
根节点：（以n=3为例）
向下搜索：
从小到大：
继续搜索，
使用过得数不再使用：
继续搜索：
我们需要输出的就是最下面这一排。
下面是代码实现：
代码：
//养成好习惯，把常用头文件包了
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;//数组大小比题目要求大就行，这题n <= 9
const int N = 10;int n;int st[N];//创建一个数组用来判断位置是否已经有数据了
bool used[N];void dfs(int u)
{//已经递归搜索到底了if(u == n){//打印数组中存放的值for(int i = 0; i < n; i++){printf("%d ", st[i]);}puts("");return;}else{for(int i = 0; i < n; i++){//如果used[i]等于true，证明该位置已经被占用，直接让i++继续循环if(!used[i]){//表示该位置已经占用used[i] = true;//将要打印的值存进数组st[u] = i + 1;//递归往下搜索dfs(u + 1);//位置恢复原样（没有被占用了）used[i] = false;}}}
}int main()
{scanf("%d", &n);dfs(0);return 0;
}AC ！！！！！！！！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。