部分和问题（搜索简单题）

部分和问题

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

难度：2

http://acm.nyist.net/JudgeOnline/problem.php?pid=1058

描述: 给定整数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

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 int n,k;
 7 int a[30];
 8 bool way[30];
 9 bool flag=0;
10 void dfs(int floor,int sum)
11 {
12     if(flag)
13         return;
14     if(sum>k)
15         return;
16     if(floor==n)
17     {
18         if(sum==k)
19         {
20             flag=1;
21             cout<<"YES"<<endl;
22             for(int i=0;i<n;i++)
23             {
24                 if(way[i])
25                     cout<<a[i]<<" ";
26             }
27             cout<<endl;
28         }
29         return;
30     }
31     way[floor]=1;
32     dfs(floor+1,sum+a[floor]);
33     way[floor]=0;
34     dfs(floor+1,sum);
35 }
36 int main()
37 {
38     int i,j;
39     freopen("in.txt","r",stdin);
40     while(cin>>n>>k)
41     {
42         flag=0;
43         memset(way,0,sizeof(way));
44         for(i=0;i<n;i++)
45             cin>>a[i];
46         dfs(0,0);
47         if(!flag)
48             cout<<"NO"<<endl;
49     }
50 }