1.对递归又有了新的理解,比如说这道题的目的是实现n个数中m个数的所有组合可能数,所以相同数字不同顺序并不能叫新的方案。
2.我们理解完题意后可以发现从1开始找到符合m个数的方案后,之后从2开始找m个数符合方案,并且从2开始的方案没有1,这是因为如果含有1,那么他一定是在1开始的方案已经包括完了。
3.由上我们可以知道我们可以慢慢递归到倒数第m个数,所有方案就已经全部找完了,并且脑海中已经能出现一个递归搜索树了,之后就是我对递归的新理解,因为递归是不断调用自己,也就是每一个新的调用函数其实是自己的子函数,也就是当子函数能完成我们的目标时,就证明这段代码放在递归入口时同样适用,这样当我们想明白最后m个数能做到我们的目标时,就不用纠结它能不能从1开始就完成我们的目标,一定是能得,如果想不明白就不用想,这段完全可以交给机器来操作。就是说我们把1到n的递归缩小到了倒数第m个数到n直接的一种方案。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=30;
int path[N];//表示每一种方案的路径
int m,n;
void dfs(int u,int start){//start是我们进入新函数的时候,从前到后当前符合条件的最小数,不重复之前的数
if(u>m){
for(int i=1;i<=m;i++){
cout<<path[i]<<" ";
}
cout<<endl;
}
else{
for(int i=start;i<=n;i++){//这个for循环有点难想明白,假设这个时候已经递归到最后一层了,
//且i是从1开始含m个数的最后一个方案,他就会结束循环向回溯到之前,一直到第一层然后i++,
//在第一层的同时,start从2开始,这样就会循环到最后,得出所有方案
path[u]=i;//保存路径
dfs(u+1,i+1);//递归下一层
path[u]=0;//恢复现场
}
}
}
int main(){
cin>>n>>m;
dfs(1,1);
return 0;
}