51Nod 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>
#include <cstdio>
using namespace std;
const int maxn = 22; int n, flag;
long long m, sum, num[maxn], s[maxn]; void dfs(int pt, long long t){
if(flag){ return; }
if(t == m){
flag = 1;
return;
}
if(t > m){
return;
}
if(t + (s[n-1]-s[pt]) < m){
return;
}
if(pt+1 < n){
dfs(pt+1, t+num[pt+1]);
dfs(pt+1, t);
}
} int main(){
freopen("in.txt", "r", stdin); while(scanf("%d %lld", &n, &m) != EOF){
sum = 0;
for(int i=0; i<n; ++i) {
scanf("%lld", &num[i]);
sum += num[i];
if(i == 0){
s[0] = num[i];
} else {
s[i] = s[i-1] + num[i];
}
}
if(sum < m){
printf("No\n");
}else{
flag = 0;
dfs(0, num[0]);
dfs(0, 0);
if(flag){
printf("Yes\n");
}else{
printf("No\n");
}
}
}
return 0;
}