[递归]组合型枚举

本文主要是介绍[递归]组合型枚举，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

​ 从 1−n 这 n 个整数中随机选取 m 个，每种方案里的数从小到大排列，按字典序输出所有可能的选择方案。

---

输入

​ 输入两个整数 n,m。（1≤m≤n≤10）

输出

​ 每行一组方案，每组方案中两个数之间用空格分隔。

​ 注意每行最后一个数后没有空格。

---

样例输入

3 2

样例输出

1 2
1 3
2 3

样例输入2

5 3

样例输出2

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

---

数据规模与约定

​ 时间限制：1 s

​ 内存限制：256 M

​ 100% 的数据保证 1≤m≤n≤10

 解题分析

创立一个函数，传入两个参数分别递归的位置和上一个位置的数字（用于确保排列是从小到大的）。

使用递归的方式实现从1到n中选取m个数的组合，并按照字典序输出所有可能的选择方案。

首先，定义全局变量n和m，分别表示给定的整数范围和选取的数的个数。还定义了一个数组nums用于存储每个方案中选取的数字，以及一个布尔数组used用于标记数字是否已经被选取。

然后，定义一个递归函数go，该函数有两个参数：pos表示当前已经选取的数字个数，num表示上一个选取的数字。递归的终止条件是当已经选取的数字个数达到m时，将当前方案输出并返回。

在递归函数中，使用一个循环来遍历所有可能的数字。对于每个数字，判断它是否已经被选取（通过used数组判断）以及是否大于上一个选取的数字。如果满足条件，将该数字标记为已选取，存储到nums数组中，并调用递归函数go继续选取下一个数字。递归函数返回后，将该数字的选取状态重置为未选取。

最后，在主函数中读取输入的n和m，并调用go函数开始递归过程。

代码实现

#include <iostream>
using namespace std;
int n,m,nums[11];
bool used[11]={0};void go(int pos,int num){if(pos>m){for(int i=1;i<=m;i++){printf("%d",nums[i]);if(i!=m) printf(" ");}printf("\n");return;}for(int i=1;i<=n;i++){if(used[i]==0 && i>num){used[i]=1;nums[pos]=i;   go(pos+1,i);used[i]=0;}}return;
}int main(){scanf("%d%d",&n,&m);go(1,0);
}

若是不要求按照从小到大的顺序，则为

#include <iostream>
using namespace std;
int n,m,nums[11];
bool used[11]={0};void go(int pos,int num){if(pos>m){for(int i=1;i<=m;i++){printf("%d",nums[i]);if(i!=m) printf(" ");}printf("\n");return;}for(int i=1;i<=n;i++){if(used[i]==0){used[i]=1;nums[pos]=i;   go(pos+1,i);used[i]=0;}}return;
}int main(){scanf("%d%d",&n,&m);go(1,0);
}

这篇关于[递归]组合型枚举的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---