苗栋栋
思路： 很显然是要遍历一遍，所以是dfs 。
我的代码：可能有些乱，但毕竟是自己写的，。。对于新手的我，还是不错的。（稍微更加理解这个bfs中的递归感觉）
#include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #include<stack> #define inf 0x3f3f3f #define M 10000+10 using namespace std; int n,r; int a[M]; int v[15]; int pre[15]; stack<int>map[M]; // 用这个存路径了 int k=0; void getroads(int ss) { while(!map[k].empty()) map[k].pop(); for(int i=0;i<r;i++) { map[k].push(ss); ss=pre[ss]; } k++; } void dfs(int num,int step) // step 表示 这已经记录几个数字 { if(step==r) //结束条件 { getroads(num); return ; } if(num==0) num=n; // else v[num]=1; for(int i=num;i>0;i--) { if(!v[i]) { pre[i]=num; dfs(i,step+1); v[i]=0; /// 回溯法 ， } } } int main() { while(~scanf("%d%d",&n,&r)) { memset(v,0,sizeof(v)); dfs(0,0); for(int i=0;i<k;i++) { while(!map[i].empty()) { printf("%d",map[i].top()); map[i].pop(); } printf("\n"); } } return 0; }
别人的代码 。。额，怎么这么简单（巧妙），怎么被我弄的这么复杂，，，可能还是需要加深理解 （多练习）把 0.0
#include <stdio.h> char res[10]; int n,r; void dfs( int x, int y){ //从x个数挑选y个 if (!y) printf( "%s\n" ,res); else { int i; for (i=x;i>=y;i--){ res[r-y] = '0' +i; dfs(i-1,y-1); //从剩下的i-1个数中挑选y-1个 } } } int main(){ scanf( "%d%d" ,&n,&r); res[r] = '\0' ; dfs(n,r); return 0; }