【AcWing】蓝桥杯备赛-深度优先搜索-dfs（2）

目录

写在前面：

题目：94. 递归实现排列型枚举 - AcWing题库

读题：

输入格式：

输出格式：

数据范围：

输入样例：

输出样例：

解题思路：

代码：

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 ！！！！！！！！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。