当前位置：首页 > article >正文

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

article 2025/1/8 3:41:20

写在前面：

题目：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

输出样例：

解题思路：

这道题是深度优先搜索的经典题目，

我们使用深度优先搜索的时候，

第一个要注意的点是，我们要保证，

我们写出的递归结构能够遍历所有情况，

在我们初学搜索的时候，我们一定要画一个递归搜索树观察，

递归非常抽象，画图能很好的帮助我们解题。（以上递归搜索的基本思路，多熟悉总是好的）

接下来是具体思路：

题目要求是在n个数里选m个，输出不同的选择方案

而且要升序排列，且字典序小的在前面，

我们先画一个递归搜索树理一下思路：

首先是根节点：（以n=5，m=3为例）

我的思路是按照位置填数据，

因为题目要求升序数组，所以第一个数只能是1，2，3。

根据题目升序的要求，

然后继续往下递归搜索：

继续递归搜索：

最后一行就是我们需要打印的值，

接下来将图形实现成代码：

代码：

//养成好习惯，把常用头文件包了
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

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;
}