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

六、非重复生成全子集组合排列(含重复数字时,生成不重复全子集组合排列)

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

Sample Input 

4  

1 2 2 3  

Sample Output 

12 

122 

1223 

123 

13 

22 

223 

23 

3  

#include<stdio.h> 
const int maxn=10; 
int n,var; 
int Index;  
int used[maxn],mat[maxn],num[maxn]; 
void push(int varNum)
{ //压栈
    for(int i=0;i<Index;++i)
    { 
        if(mat[i]==varNum)
        { 
            ++used[i]; 
            return;  
        } 
    }  
    mat[Index]=varNum; 
    ++used[Index++]; 
}  
void solve(int l,int p)
{  //求解
    for(int i=0;i<l;++i)
        printf("%d", num[i]); 
    if(l) puts(""); 
    for(int i=p;i<Index;++i)
    { 
        if(used[i])
        { 
            used[i]--;   
            num[l]=mat[i]; 
             solve(l+1,i); 
            used[i]++; 
        } 
    } 
}
int main()
{  
    while(scanf("%d", &n)!=EOF)
    { 
        Index=0;  
        for(int i=0;i<n;++i)
        { 
            scanf("%d", &var); 
            push(var); 
        }  
        solve(0,0); 
    }  
    return 0; 
}  

注意:倘若需要输出空集(也即输出一个换行),可做如下修改

在函数solve()中,将if(l)puts(""); 改为puts(""); 


上一篇:快速排序的非递归实现 -- 人人网2014笔试题目


下一篇:JAVA 设计模式 备忘录模式