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

解题思路:

砝码有三种状态：左，右，不放。



注意事项:





参考代码:

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int a[26],sum[26]={0};
int flag=0;
void dfs(int s,int k){
	if(flag==1)return;
	if(abs(s)>sum[k])return;
	if(s==0||abs(s)==sum[k]){
		flag=1;
		return;
	}
	if(k<0){
		return;
	}
	dfs(s-a[k],k-1);
	dfs(s,k-1);
	dfs(s+a[k],k-1);
	return;
}
int main()
{	
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(i>0)sum[i]=sum[i-1]+a[i];
		else sum[0]=a[0]; 
	}
	while(m--){
		int s;
		cin>>s;
		flag=0;
		dfs(s,n-1);
		if(flag==1)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
    return 0;
}