不重复组合

输入n个数，求这n个数构成的集合的所有子集，不允许输出重复的项

输入

1 1 3

输出

1 1

1 1 3

1 3

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxn = 100;
 5 int rcd[maxn],num[maxn],vis[maxn];
 6 int n,m;
 7 int read_input()
 8 {
 9     if(scanf("%d",&n)==EOF)
10         return 0;
11     m=0;
12     memset(vis,0,sizeof(vis));
13     int i,j;
14     for( i=0;i<n;i++){
15         int val;
16         scanf("%d",&val);
17         for( j=0;j<m;j++)
18             if(num[j]==val){
19                 vis[j]++;
20                 break;
21             }
22         if(j==m){
23             num[j]=val;
24             vis[m++]++;
25         }
26 
27     }
28     return 1;
29 }
30 void unrepeat(int l,int p){
31 
32 
33     for(int i=0;i<l;i++){
34         printf("%d",rcd[i]);
35         if(i<l-1)
36             printf(" ");
37     }
38     printf("
");
39 
40     for(int i=p;i<m;i++)
41         if(vis[i]>0){
42             vis[i]--;
43             rcd[l]=num[i];
44             unrepeat(l+1,i);
45             vis[i]++;
46         }
47 
48 }
49 int main(){
50     while(read_input())
51         unrepeat(0,0);
52 
53     return 0;
54 }

View Code

引用别人说的话：“搜索问题中很多本质上是排列组合问题，只不过加上了某些剪枝和限制条件，解这类题的基本算法框架常常是类循环排列，劝排列，一般组合或者全组合，而不重复排列和不重复组合则是两种非常有效的剪枝技巧”