[递归]组合型枚举

题目描述

? 从?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);
}