蓝桥杯算法提高VIP-盾神与砝码称重 （C++代码）

解题思路:

注意事项:

参考代码:

dfs不超时是没有想到的

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long LL;
int n,m,A[25],w[11],res;
void dfs(int dep,LL sum,int& res,int w)
{
	if(res) return;//如果找到了合适的称量方法，直接返回，不用继续搜索 
	if(sum==w)//如果满足重量 
	{
		res=true;
		return ;
	}
	if(dep<=n)
	{
		dfs(dep+1,sum+A[dep],res,w);
		dfs(dep+1,sum,res,w);
		dfs(dep+1,sum-A[dep],res,w);	
	} 
} 
int main(void)
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>A[i];
	for(int i=1;i<=m;i++) cin>>w[i];
	for(int i=1;i<=m;i++)
	{
		res=false;
		dfs(1,0,res,w[i]);
		if(res) cout<<"YES"<<endl;
		else cout<<"NO"<<endl; 
	}
	return 0;
}