部分和

部分和问题

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

///////////

#include<stdio.h>#include<string.h>int n,k;bool flag=0;int a[20],b[20];void dfs(int i,int sum){if(i>n||flag)return;if(sum==k){flag=1;return;}b[i+1]=1;dfs(i+1,sum+a[i+1]);if(!flag)b[i+1]=0;dfs(i+1,sum);}int main(){while(~scanf("%d %d",&n,&k)){flag=0;memset(b,0,sizeof(b));for(int j=1; j<=n; j++)scanf("%d",&a[j]);dfs(0,0);if(flag)PRintf("YES/n");elseprintf("NO/n");for(int i=1; i<=n; i++)if(b[i])printf("%d ",a[i]);printf("/n");}return 0;}