当前位置：首页 > news >正文

找出n个自然数（1,2,3，……，n）中取r个数的组合。

news 2025/3/21 23:22:24

题目：找出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;
}