hdu 1258 Sum It Up

Sum It Up

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1258

题目的意思：给一个sum的值，给一个n，接下来有n个数

这几个数随机组合等于sum时，输出怎么样组合的。

注意：不能有重复的

解题思路：用DFS深搜，这个我写的时候都把自己搞晕了，看了别人的思路才憋出来，屡思路就屡了半天，还是去重的地方理解不深，还是太水啊

Sample Input

4 6 4 3 2 2 1 1

5 3 2 1 1

400 12 50 50 50 50 50 50 25 25 25 25 25 25

0 0

Sample Output

Sums of 4:

3+1

2+2

2+1+1

Sums of 5:

NONE

Sums of 400:

50+50+50+50+50+50+25+25+25+25

50+50+50+50+50+25+25+25+25+25+25

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<queue>
 6 #include<cmath>
 7 #include<algorithm>
 8 using namespace std;
 9 int sum,n,flag;
10 int a[15],b[15],vis[15];
11 bool cmp(int a,int b)
12 {
13     return a>b;
14 }
15 void dfs(int x,int y,int z)
16 {
17     int i,j=0;
18     if(y>sum)
19     return ;
20     if(y==sum)
21     {
22         flag=0;
23         for(i=0;i<x;i++)
24         {
25             if(i==0)
26             printf("%d",b[i]);
27             else
28             printf("+%d",b[i]);
29         }
30         printf("
");
31         return ;
32     }
33     for(i=z;i<n;i++)
34     {
35         if(!vis[i])
36         {
37             vis[i]=1;
38             b[x]=a[i];
39             dfs(x+1,y+a[i],i+1);
40             vis[i]=0;
41             while(a[i]==a[i+1])//去重
42             i++;
43         }
44     }
45 }
46 
47 
48 int main()
49 {
50     int i;
51     while(~scanf("%d%d",&sum,&n))
52     {
53         memset(vis,0,sizeof(vis));
54         if(!sum&&!n)
55         break;
56         for(i=0;i<n;i++)
57         scanf("%d",&a[i]);
58         sort(a,a+n,cmp);
59         flag=1;
60         printf("Sums of %d:
",sum);
61         dfs(0,0,0);
62         if(flag)
63         {
64             printf("NONE
");
65         }
66     }
67     return 0;
68 }

View Code