NYOJ 1058 部分和问题

部分和问题

时间限制：1000 ms | 内存限制：65535 KB

难度：2

描述: 给定整数a1、a2、.......an，判断是否可以从中选出若干数，使它们的和恰好为K。

输入

首先，n和k，n表示数的个数，k表示数的和。
接着一行n个数。
（1<=n<=20,保证不超int范围）

输出

如果和恰好可以为k，输出“YES”，并按输入顺序依次输出是由哪几个数的和组成，否则“NO”

样例输入

4 13
1 2 4 7

样例输出

YES
2 4 7

原题来自：http://acm.nyist.net/JudgeOnline/problem.php?pid=1058

分析如下：

从num[0]开始按顺序决定每个数加或者不加，在全部N个数都决定后在判断他们的和是不是和k相等。

因为状态数是2^{n+1 ，}所以复杂度是O(2ⁿ)。

代码如下：

 1 #include <stdio.h>
 2 
 3 int n,k,pos;
 4 int num[25];   // 输入的数据 
 5 int TTT[25];   // 哪几个数构造的数组 
 6 
 7 bool dfs(int i,int sum)
 8 {
 9     if(i==n)return sum==k;
10     else if(sum>k)return false;
11     //不+情况 
12     if(dfs(i+1,sum))return true;
13     //+的情况
14     if(dfs(i+1,num[i]+sum))
15     {
16         TTT[pos++]=num[i];
17         return true;
18     }
19     return false;
20 }
21 
22 int main()
23 {
24     while(~scanf("%d%d",&n,&k))
25     {
26         pos=0;
27         for(int i=0;i<n;i++)
28             scanf("%d",&num[i]);
29         if(dfs(0,0))
30         {
31             printf("YES
");
32             for(int i=pos-1;i>0;i--)
33                 printf("%d ",TTT[i]);
34             printf("%d
",TTT[0]);
35         }
36         else printf("NO
");
37     }
38     return 0;
39 }