组合数
时间限制:3000 ms | 内存限制:65535 KB
难度:3
- 描述
- 找出从自然数1、2、... 、n(0<n<10)中任取r(0<r<=n)个数的所有组合。
- 输入
- 输入n、r。
- 输出
- 按特定顺序输出所有组合。
特定顺序:每一个组合中的值从大到小排列,组合之间按逆字典序排列。 - 样例输入
-
5 3
- 样例输出
-
543 542 541 532 531 521 432 431 421 321
-
/*
题解:DFS入门题
*/
#include<cstdio> #include<cstring> int a[12],b[12],vis[12],n,r; void dfs(int step) { if(step==r) { for(int i=0; i<r; i++) printf("%d",b[i]); printf("\n"); return; } for(int i=1; i<=n; i++) { if(!vis[i]&&(a[i]<b[step-1]||step==0)) { vis[i]=1; b[step]=a[i]; dfs(step+1); vis[i]=0; } } } int main() { while(scanf("%d %d",&n,&r)!=EOF) { for(int i=1; i<=n; i++) { a[i]=n-i+1; } memset(vis,0,sizeof(vis)); dfs(0); } return 0; }