正方形(c++题解)

题目描述

给定一组不同长度的木棍，是否有可能将它们端对端地连接起来形成  个正方形?

输入格式

第1行输入包含N，即测试数据的数量。 每组测试数据第一个数为 ，即木棒的根数。之后有  个整数， 每个都给出了一根棍子的长度 。

输出格式

对于每种情况，如果可以形成正方形，则输出 yes 或 no，每个结果占  行。

样例

样例输入

复制3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5

样例输出

复制yes
no
yes

_____________________________________________________________________________

写作不易，点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 

_____________________________________________________________________________

#include <bits/stdc++.h> 
using namespace std; 
int a[100],v[100],n,len,cnt,z;
bool dfs(int s,int c,int l){
	if(s>cnt)return true;
	if(c==len)return dfs(s+1,0,1);
	int g=0;
	for(int i=l;i<=n;i++){
		if(!v[i]&&c+a[i]<=len&&g!=a[i]){
			v[i]=1;
			if(dfs(s,c+a[i],i+1)) return true;
			g=a[i];
			v[i]=0;
			if(c==0||c+a[i]==len) return false;
		}
	}
	return false;
}
int main(){
	cin>>z;
	for(int c=1;c<=z;c++){
		cin>>n;
		int sum=0,ans=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			sum+=a[i];
			ans=max(ans,a[i]);
		}
		sort(a+1,a+1+n);
		reverse(a+1,a+n+1);
		for(len=ans;len<=sum;len++){
			if(sum%len)continue;
			cnt=sum/len;
			memset(v,0,sizeof(v));
			if(dfs(1,0,1)) break;
		}
		if(len*4==sum)cout<<"yes\n";
		else cout<<"no\n";
	}
}