找出n个自然数（1,2,3，……，n）中取r个数的组合。
题目：找出n个自然数（1,2,3，……，n）中取r个数的组合。例如，当n=5，r=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
首先，找到所有的组合（不从小到大排）：
#include<iostream>
using namespace std;
int n,r;
int cnt=0;
int a[10];
bool vis[10];
void dfs(int x){
if(x==r){
for(int i=0;i<cnt;i++){
cout<<a[i]<<" ";
}
cout<<endl;
return ;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
vis[i]=true;
a[cnt++]=i;
dfs(x+1);
cnt--;
vis[i]=false;
}
}
}
int main(){
cin>>n>>r;
dfs(0);
return 0;
} 
增加一个参数，使之从小到大排序：
#include<iostream>
using namespace std;
int n,r;
int cnt=0;
int a[10];
bool vis[10];
void dfs(int x,int start){// 添加一个 start 参数
if(x==r){
for(int i=0;i<cnt;i++){
cout<<a[i]<<" ";
}
cout<<endl;
return ;
}
for(int i=start;i<=n;i++){// 从 start 开始
if(!vis[i]){
vis[i]=true;
a[cnt++]=i;
dfs(x+1,i+1);// 下一层开始时，从 i + 1 开始，保证增序
cnt--;
vis[i]=false;
}
}
}
int main(){
cin>>n>>r;
dfs(0,1); // 每一次调用dfs选一个数，选r次，从0开始计数；从 1 开始选
return 0;
} 
递归写法：
#include<iostream>
using namespace std;
int a[100];
void comb(int n,int r){
for(int i=n;i>=r;i--){
a[r]=i;
if(r>1){
comb(i-1,r-1);
}else{
for(int i=a[0];i>=1;i--){
cout<<a[i]<<" ";
}
cout<<endl;
}
}
}
int main(){
int n,r;
cin>>n>>r;
a[0]=r;
comb(n,r);
return 0;
}
思路：n=5，r=3时，先考虑从大到小排列。固定5，只需求n=4，r=2，共6种；固定4，只需求n=3，r=2；固定3，只需求n=2，r=2. 最后只需逆序输出即可。
原文地址：https://blog.csdn.net/m0_73801775/article/details/142750439
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！