回溯加剪枝

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <map>

#include <set>

#include <sstream>

#include <string>

#include <cstring>

#include <algorithm>

#include <iostream>

#define maxn 1000010

#define INF 0x7fffffff

#define inf 10000000

#define ull unsigned long long

#define ll long long

using namespace std;

int a[30], n;

bool vis[30];

bool dfs(int cur, int now, int aim, int k)

{

    if(cur == 3) return true;

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

    {

        if(!vis[i] && now > a[i])

        {

            vis[i] = 1;

            if(dfs(cur, now-a[i], aim, i+1))

                return true;

            vis[i] = 0;

        }

        else if(!vis[i] && now == a[i])

        {

            vis[i] = 1;

            if(dfs(cur+1, aim, aim, 0))

                return true;

            vis[i] = 0;

        }

    }

    return false;

}

int main()

{

    int t, sum;

    scanf("%d", &t);

    while(t--)

    {

        sum = 0;

        int _max = 0;

        memset(vis, 0, sizeof(vis));

        scanf("%d", &n);

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

        {

            scanf("%d", &a[i]);

            sum += a[i];

            _max = max(_max, a[i]);

        }

        if(sum % 4 || _max > sum/4)

            puts("no");

        else

        {

            if(dfs(0, sum/4, sum/4, 0)) puts("yes");

            else puts("no");

        }

    }

    return 0;

}