51nod 1268 和为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 <bitsstdc++.h> 
using namespace std;
typedef long long ll;


int a[22];
int n,k;

bool flag = false;

void dfs(int x ,int k){
    if(k == 0){
        flag = true;
        return;
    }
    if(flag) return;
    if(x == n) return;
    if(k < 0) return;
    dfs(x+1,k);
    dfs(x+1,k-a[x]);
}


int main() {
 
  cin >> n >> k;
    for(int i = 0;i < n; i++){
        cin >> a[i];
    }
    dfs(0,k);
    if(flag) cout << "Yes" << endl;
    else cout << "No" << endl;
  return 0;
}
//  writen by zhangjiuding