目录
写在前面：
题目：92. 递归实现指数型枚举 - AcWing题库
读题：
输入格式：
输出格式：
数据范围：
输入样例：
输出样例：
解题思路：
代码：
AC ！！！！！！！！！！
写在最后：
写在前面：
距离蓝桥杯已经不足一个月了，
根据江湖上的传言，
蓝桥杯最喜欢考的是深度优先搜索和动态规划，
所以蓝桥杯也叫暴搜杯、dp杯，
那我备赛当然也就从深度优先搜索，也就是所谓的dfs开始。
题目：92. 递归实现指数型枚举 - AcWing题库
读题：
输入格式：
输入一个整数 n。
输出格式：
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好 11 个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
数据范围：
1 ≤ n ≤ 15
输入样例：
3
输出样例：
3
2
2 3
1
1 3
1 2
1 2 3
解题思路：
这道题是深度优先搜索的经典题目，
我们使用深度优先搜索的时候，
第一个要注意的点是，我们要保证，
我们写出的递归结构能够遍历所有情况，
在我们初学搜索的时候，我们一定要画一个递归搜索树观察，
递归非常抽象，画图能很好的帮助我们解题。（以上递归搜索的基本思路，多熟悉总是好的）
接下来是具体思路：
题目要求我们随机选取输出每种方案，而且要求升序输出。
我们根据要求，画出对应的搜索树：（以n=3为例）
首先是根节点：
递归搜索：
因为题目要求是升序数组，所以从第二个位置开始，
就只能填2，再下一个就得填3，以满足题目要求：
继续搜索：
如果位置已经使用过了，就搜索下一个位置，
没有位置就停下。
最后：
我们根据画出来的搜索树写代码：
代码：
//养成好习惯，先把常用头文件包了
#include
#include
#include
#include
using namespace std;
//数组的大小，比题目要求大即可（题目要求n是小于等于15的）
const int N = 20;
//全局变量的数组会把数组元素初始化成0
int st[N];
//这个是需要输入的变量
int n;
void dfs(int u)
{
//数组已经存了n个数，达成条件就可以打印了
if(u == n)
{
for(int i = 0; i < n; i++)
{
//st数组元素 == 1 表示这个位置需要输出
if(st[i] == 1)
{
printf("%d ", i + 1);
}
}
puts("");
return;
}
else
{
//把数组设为1表示该位置写入了数据
st[u] = 1;
dfs(u + 1);
st[u] = 0;
//把数组设为2表示该位置为空
st[u] = 2;
dfs(u + 1);
st[u] = 0;
}
}
int main()
{
scanf("%d", &n);
dfs(0);
return 0;
}
AC ！！！！！！！！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。
精彩内容
您阅读本篇文章共花了：
发表评论