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 <bits\stdc++.h>

using namespace std;

typedef long long ll;

int a[];

int n,k;

bool flag = false;

void dfs(int x ,int k){

    if(k == ){

        flag = true;

        return;

    }

    if(flag) return;

    if(x == n) return;

    if(k < ) return;

    dfs(x+,k);

    dfs(x+,k-a[x]);

}

int main() {

  cin >> n >> k;

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

        cin >> a[i];

    }

    dfs(,k);

    if(flag) cout << "Yes" << endl;

    else cout << "No" << endl;

  return ;

}

//  writen by zhangjiuding