六、非重复生成全子集组合排列(含重复数字时,生成不重复全子集组合排列)
对于搜索的深度很深或深度不固定的情况,则无法用枚举的方法来设置循环嵌套的层数,这时可以考虑用递归法来完成搜索任务。递归是一种常用算法,它是搜索的另一种实现方式。如果在算法设计中采用一个函数或过程直接或间接地调用它自身来解决问题的方法,则称该方法为递归算法。递归算法必须要设计好一个或若干个确定的递归终止条件。Sample Input
4
1 2 2 3
Sample Output
1
12
122
1223
123
13
2
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("");