ACM 10364 Q10364: Square
作法 : DFS
須知:1.需要先排序來減少搜尋的次數
2.把不可能的組合直接做判斷
3.儘可能減少搜尋的次數...
/***********************************************************/
#include<stdio.h>
#include<stdlib.h>
int n,num[50],find;
int appear[50]={0};
void DFS (int now,int sum,int end,int start)
{
int a;
if(now==3) {find=1;return;}
if(sum==end) DFS(now+1,0,end,0);
if(sum>=end||find==1) return;
for(a=start;a<n;a++)
if(appear[a]==0)
{
appear[a]=1;
DFS(now,sum+num[a],end,a+1);
appear[a]=0;
}
}
main()
{
int t,a,b,c;
while(scanf("%d",&t)==1)
while(t--)
{
scanf("%d",&n);
int sum=0,max=0;
for(a=0;a<n;a++)
{
scanf("%d",&num[a]);
if(max<num[a]) max=num[a];
sum=sum+num[a];
}
for(a=0;a<n;a++)
{
c=a;
for(b=a+1;b<n;b++)
if(num[b]>num[c]) c=b;
int temp;
temp=num[a];
num[a]=num[c];
num[c]=temp;
}
find=0;
if(sum!=0&&sum%4==0&&max<=sum/4)
DFS(0,0,sum/4,0);
if(find==1) printf("yes\n");
else printf("no\n");
}
return 0;
}