题目描述
从 1~n 这 n 个整数中随机选出 m 个,输出所有可能的选择方案。
输入格式
两个整数 n,m ,在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案,每行1个。
首先,同一行内的数升序排列,相邻两个数用一个空格隔开。
其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面(例如1 3 5 7排在1 3 6 8前面)。
数据范围
n>0 ,
0≤m≤n ,
n+(n−m)≤25
输入样例
5 3
输出样例
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
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
//此题与上题相比,只有递归出口发生了变化
int n,m;
int a[30];//存放数
int vis[30];//选择为1,不选择为2 ,还没判断为0
int cnt=0;
void dfs(int x){
if(x==n+2){
return;
}
if(cnt==m){//一种方案结束
for(int i=1;i<=n;i++){
if(vis[i]==1){//选择的,即是1的输出
cout << a[i] << " ";
}
}
cout << endl;
return;
}
vis[x]=1;//选
cnt++;
dfs(x+1);//下一个数
vis[x]=0;//回溯
cnt--;
vis[x]=2;//不选
dfs(x+1);//下一个数
vis[x]=0;//回溯
}
int main()
{
cin >> n >> m;
for(int i=1;i<=n;i++){
a[i]=i;//初始化
}
dfs(1);//从数字1开始判断(1~n)
return 0;
}