对于搜索的深度很深或深度不固定的情况,则无法用枚举的方法来设置循环嵌套的层数,这时可以考虑用递归法来完成搜索任务。递归是一种常用算法,它是搜索的另一种实现方式。如果在算法设计中采用一个函数或过程直接或间接地调用它自身来解决问题的方法,则称该方法为递归算法。递归算法必须要设计好一个或若干个确定的递归终止条件。
五、生成全子集组合排列(不含空集)
Sample Input
4
1 2 3 4
Sample Output
1
12
123
1234
124
13
134
14
2
23
234
24
3
34
4
#include<stdio.h> const int maxn=10; int n; int mat[maxn]; int num[maxn]; void solve(int cur_totalVar,int nextVar) { for(int i=0;i<cur_totalVar;++i) printf("%d",num[i]); if(cur_totalVar) puts(""); for(int i=nextVar;i<n;++i) { num[cur_totalVar]=mat[i]; solve(cur_totalVar+1,i+1); } } int main() { while(scanf("%d", &n)!=EOF) { for(int i=0;i<n;++i) scanf("%d",mat+i); solve(0,0); } return 0; }
注意:倘若需要输出空集(也即输出一个换行),可做如下修改
在函数solve()中,将if(cur_totalVar)puts(""); 改为puts("");