题目 1548: [蓝桥杯][算法提高VIP]盾神与砝码称重

时间限制: 1Sec 内存限制: 128MB 提交: 782 解决: 331

题目描述
有一天，他在宿舍里无意中发现了一个天平！这 个天平很奇怪，有n个完好的砝码，但是没有游码。盾神为他的发现兴奋不已！于是他准备去称一称自己的东西。他准备好了m种物品去称。神奇的是，盾神一早就 知道这m种物品的重量，他现在是想看看这个天平能不能称出这些物品出来。但是盾神稍微想了1秒钟以后就觉得这个问题太无聊了，于是就丢给了你。

数据规模和约定
1< =n< =24, 1< =m< =10.
输入
第一行为两个数，n和m。
第二行为n个数，表示这n个砝码的重量。
第三行为m个数，表示这m个物品的重量。
输出
输出m行，对于第i行，如果第i个物品能被称出，输出YES否则输出NO。
样例输入
4 2
1 2 4 8
15 16
样例输出
YES
NO

天平分两边，一边放砝码，一放物品。
砝码三种情况 ①两边都不放 ②放砝码那边 ③放物品那边

//
// Created by hyf on 2020/8/6.
//
#include<bits/stdc++.h>
using namespace std;
const int MAX_N=10000;
int n,k,m;
int a[MAX_N];
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;
    if(dfs(i+1,sum-a[i]))return true;
    return false;
}
void solve()
{
    for(int i=1;i<=m;i++)
    {
        cin>>k;
        if(dfs(0,0))printf("YES\n");
        else printf("NO\n");
    }
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    solve();
}