51nod1268 和为K的组合（DFS）

1268 和为K的组合 

基准时间限制：1 秒 空间限制：131072 KB 分值: 20 难度：3级算法题

 收藏

 关注

给出N个正整数组成的数组A，求能否从中选出若干个，使他们的和为K。如果可以，输出："Yes"，否则输出"No"。

Input

第1行：2个数N, K, N为数组的长度, K为需要判断的和(2 <= N <= 20，1 <= K <= 10^9)

第2 - N + 1行：每行1个数，对应数组的元素A[i] (1 <= A[i] <= 10^6)

Output

如果可以，输出："Yes"，否则输出"No"。

Input示例

5 13

2

4

6

8

10

Output示例

No

李陶冶 (题目提供者)

 

 数据比较水，直接dfs

 #include<iostream>

 using namespace std;

 long long int n,a[],m;

 int flag=,v[]={};

 void dfs(long long int sum,int t)

 {

     //cout<<sum<<endl;

     if(sum==m)

     {

         flag=;

         return;

     }

     if(flag||sum>m||t>n)

     return;

     dfs(sum+a[t],t+);

     dfs(sum,t+);

 }

 int main()

 {

     scanf("%lld%lld",&n,&m);

     long long int sum=;

     for(int i=;i<=n;i++)

     {

         scanf("%lld",&a[i]);

         sum+=a[i];

     }

     if(sum<m)

     printf("No\n");

     else if(sum==m)

     printf("Yes\n");

     else

     {

         flag=;

         dfs(,);

         if(flag)

         printf("Yes\n");

         else

         printf("No\n");

     }

     return ;

 }