递归求解几类排列组合问题(五、生成全子集组合排列)

对于搜索的深度很深或深度不固定的情况,则无法用枚举的方法来设置循环嵌套的层数,这时可以考虑用递归法来完成搜索任务。递归是一种常用算法,它是搜索的另一种实现方式。如果在算法设计中采用一个函数或过程直接或间接地调用它自身来解决问题的方法,则称该方法为递归算法。递归算法必须要设计好一个或若干个确定的递归终止条件。

五、生成全子集组合排列(不含空集)

Sample Input 

4  

1 2 3 4  

Sample Output 

12 

123 

1234 

124 

13 

134 

14 

23 

234 

24 

34 

#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(""); 

上一篇:微信JS SDK Demo (下)


下一篇:Android-telephony各文件解释 电话系统之rilD Android电话系统之RIL-Java