部分和问题(dfs)

部分和问题

时间限制：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


用dfs走一遍,注意要多组输入,(但是题目没提示,有毒)

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #define N 30
 5 using namespace std;
 6 int k[N];
 7 bool vis[N];
 8 int n,m,sum=0;
 9 bool prime;
10 void dfs(int pos){
11     if(prime)
12         return ;
13     if(sum>=m){
14         if(sum==m){
15             printf("YES
");
16             prime=true;
17             for(int i=0;i<n;i++){
18                 if(vis[i])
19                     printf("%d ",k[i]);
20             }
21             printf("
");
22         }
23         return;
24     }
25     for(int i=pos;i<n;i++){
26         sum+=k[i];
27         vis[i]=1;
28         dfs(i+1);
29         sum-=k[i];
30         vis[i]=0;
31     }
32 }
33 int main(){
34     while(~scanf("%d%d",&n,&m)){
35         for(int i=0;i<n;i++){
36             scanf("%d",&k[i]);
37         }
38         memset(vis,0,sizeof(vis));
39         prime=false;
40         sum=0;
41         dfs(0);
42         if(!prime)
43             printf("NO
");
44     }
45     return 0;
46 }