10年9月17号Update…
状态压缩BFS 40行水过.. 代码是POJ2362的, 一样的题.. 原来本文只有1011

#include <stdio.h>

bool dfs(int a[],int u,int n,int __s,int start)
{
    if (start==n)
        return true;
    for(int i=(1<<start);i<(1<<n);i+=(2<<start)) {
        if(i&u)
            continue;
        int count=0;
        for(int j=0;j<n;j++)
            count+=a[j]*((i>>j)&1);
        if(count!=__s)
            continue;

        int __u=u|i;
        int j;
        for(j=0;j<n && ((__u>>j)&1);j++);
        if(dfs(a,__u,n,__s,j)) {
            /* DEBUG
            for(int k=0;k<n;k++)
                if((i>>k)&1)
                    printf("%d ",a[k]);
            printf("\n");   */
            return true;
        }
    }
    return false;
}


int main()
{
    int N;
    scanf("%d",&N);
    while (N--)
    {
        int n,a[21],count=0;
        scanf("%d",&n);
        for (int i=0;i<n;i++)
        {
            scanf("%d",a+i);
            count+=a[i];
        }
        printf("%s\n",count%4?"no":(dfs(a,0,n,count/4,0)?"yes":"no"));
    }
    return 0;
}

Continue reading →