51Nod：1268 和为K的组合

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

李陶冶 (题目提供者)

C++的运行时限为：1000 ms ，空间限制为：131072 KB 示例及语言说明请按这里

时间复杂度：O（2^n）

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6;

int a[maxn];

int n,k;

bool dfs(int i,int sum)

{

	if(i==n) return sum==k;

	if(dfs(i+1,sum)) return true;

	if(dfs(i+1,sum+a[i])) return true;

	return false;

}

int main()

{

	cin>>n>>k;

	for(int i=0;i<n;i++) cin>>a[i];

	if(dfs(0,0)) cout<<"YES\n";

	else cout<<"NO\n";

	return 0;

}