hdu1258Sum It Up

这题主要是重复问题怎么删除由于是排好序的有重复的肯定是相邻的

在同一层上的结点值保证不相同就行不同层可以相同比如 4 = 2+1+1 可以有两个1

具体看代码

View Code

 1 #include <stdio.h>
 2 #include<string.h>
 3 int a[1001],n,s,v,y,flag,num[1001],ch;
 4 void dfs(int x, int i,int v)
 5 {
 6     int j,k;
 7     y+= x;
 8     num[v] = x;
 9     if(y == s)
10     {
11             for(k = 1 ; k < v; k++)
12             printf("%d+",num[k]);
13             printf("%d\n",num[v]);
14             flag = 1;
15     }
16     else
17     {
18         for(j = i+1 ; j <= n ; j++)
19         {
20             if(a[j]!=a[j-1]||j == i+1)//同一层结点值不同或者不同层
21             {
22                 if(y+a[j]<=s)
23                 {
24                     dfs(a[j],j,v+1);
25                     y-=a[j];
26                 }
27             }
28 
29         }
30     }
31 }
32 int main()
33 {
34     int i, j;
35     while(scanf("%d%d", &s,&n)&&s&&n)
36     {
37         flag = 0;
38         for(i = 1 ; i <= n ; i++)
39             scanf("%d",&a[i]);
40         printf("Sums of %d:\n",s);
41         a[0] = -1;
42         for(i = 1 ; i <= n ; i++)
43             if(a[i]!=a[i-1]&&a[i]<=s)
44             {
45                 y = 0;
46                 dfs(a[i],i,1);
47             }
48         if(!flag)
49         printf("NONE\n");
50     }
51     return 0;
52 }