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