每日算法打卡：递归实现组合型枚举

算法
1.1k words

原题链接

93. 递归实现组合型枚举

题目难度：简单

题目来源：《算法竞赛进阶指南》

题目描述

从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。

输入格式

两个整数 n,m 在同一行用空格隔开。

输出格式

按照从小到大的顺序输出所有方案，每行 1 个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。

数据范围

n>0 ,
0≤m≤n ,
n+(n−m)≤25

输入样例：

1
5 3

输出样例：

1
2
3
4
5
6
7
8
9
10
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个数，不考虑顺序

首先考虑在手算情况下是如何确保不重不漏的枚举出所有情况的，例如从1到5这5个数字中选取3个数字，一种比较容易想到的方法就是，优先取最小的数字填入左边的两个空位，第三个空位依次枚举，枚举完成之后，换掉第二个位置的数字，依次枚举

这里就出来一个问题，如何保证这样的枚举方式是不重不漏呢，主要是重复的问题，其实只需要确保每次选择数字时，选择的数字比前一个数字大即可，这样就可以保证序列一定是升序的，并且没有重复的数字

那么想要使用递归来实现这个过程，就需要把他转换成树的形式

同样是5选3

屏幕截图 2024-01-04 102410.png

这里可以发现，按照一开始确定的后选的数字要比前选的数字大的规定，第一个位置填4和5实际上是不符合情况的

在画完递归搜索树之后，要将其转化为代码，核心思想其实就在于需要传入什么样的参数，当然这里的参数可能是作为全局变量的直接使用的，有些参数则需要自己手动传入，对于递归函数参数设计其实就是经验问题了

具体到这个问题上，首先需要知道三个位置的状态（是否填入数字以及填入的数字是几），可以通过开一个数组来记录，其次需要知道，当前应该选择哪个位置的数据，只需要传入一个变量即可，最后需要知道还有哪些数字可以被选择，可以传入一个数值，代表当前可以从这个数开始枚举

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
using namespace std;

const int N = 30; // 数据范围

int n, m;
int state[N]; // 状态数组，用于记录方案

void dfs(int cur, int start) // 表示当前应该枚举第cur个位置的数字，可以选择大于等于start的数字
{
    if (cur + n - start < m)
        return; // 优化
    if (cur > m) // 边界情况，当已经选择了m个数
    {
        // 输出结果
        for (int i = 1; i <= m; i++)
            cout << state[i] << ' ';
        cout << '\n';
        return;
    }

    for (int i = start; i <= n; i++)
    {
        state[cur] = i; // 选择数据
        dfs(cur + 1, i + 1); // 递归
        state[cur] = 0; // 恢复原状
    }
}

int main()
{
    cin >> n >> m;
    dfs(1, 1); // 表示从第1个位置开始枚举，可以选择大于等于1的数字
    return 0;
}

优化

我们在之前分析的时候发现，有些情况是可以直接忽略而不用进行递归的，我们选择的数字是从start到n的，如果当start到n的所有数字都选上也不够要求的剩下空位个数字，就是不符合情况，可以特判直接退出的

Comments