使用递归解决编程题

题目：递归实现组合型枚举

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

输入

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

输出

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

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

样例输入1

3 2

样例输出1

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

参考答案

#include <iostream>
using namespace std;

int arr[10];

// 按照字典序输出，也就是枚举的时候要从小到大进行枚举 
void print_one_result(int n){
	for(int i=0;i<n;i++){
		if(i) cout<<" ";
		cout << arr[i];
	}
	cout<<endl;
	return;
}

void f(int i,int j,int n,int m){
	// 递归条件为：i==m，也就是已经枚举了m位
	if(i==m){
		print_one_result(m);
		return;
	} 
	// 关键剪枝： m-i-1<=n-k
	// m - i -1：还需要选择的数字个数
	// n - k：剩余可用数字的数量 
	for(int k=j;k<=n&&m-i-1<=n-k;k++){
		arr[i]=k;
		f(i+1,k+1,n,m);
	}
	return;
}

int main(){
	int n,m;
	cin>>n>>m;
	// 0代表当前的位置，1代表可以枚举的最小的数字
	// n代表最大可以枚举的数字，m代表枚举多少个数字即可停止 
	f(0,1,n,m);
	return 0;
}

 题目来源网站：HZOJ - Online Judge 

文章创作不易，写的很详细，每一个字每一行代码都是自己亲自敲的，这也让我花了很多时间。最后，如果觉得本文对大家有帮助的话，还请给我点个赞和关注，谢谢大家！！！