Problem Description

Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?

 

Input

The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000.

 

Output

For each case, output a line containing "yes" if is is possible to form a square; otherwise output "no".

 

Sample Input

 

Sample Output

 

Source

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

int a[];

bool vis[];

int n,ave;

bool flag;

void dfs(int num,int len,int start)

{

    if(flag)

    return;

    if(num==)

    {

        flag=true;

        return;

    }

    if(len==ave)

    {

        dfs(num+,,);

        if(flag)

            return;

    }

    for(int i=start;i<n;i++)

    {

        if(!vis[i]&&len+a[i]<=ave)

        {

            vis[i]=true;

            dfs(num,len+a[i],i+);

            vis[i]=false;

            if(flag)

                return;

        }

    }

}

int main()

{

    int t;

    cin>>t;

    while(t--)

    {

        cin>>n;

        int sum=,maxlen=;

        for(int i=;i<n;i++)

        {

            cin>>a[i];

            sum+=a[i];

            if(a[i]>maxlen)

                maxlen=a[i];

        }

        ave=sum/;

        if(sum%!=||maxlen>ave)

        {

            cout<<"no"<<endl;

            continue;

        }

        sort(a,a+n);

        memset(vis,,sizeof(vis));

        flag=false;

        dfs(,,);

        if(flag)

            cout<<"yes"<<endl;

        else

            cout<<"no"<<endl;

    }

}