K_程式人

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1305

#include<cstdio>

#include<algorithm>

using namespace std;

bool dfs(int sum, int x, int y, int l, int m, int a[], int c[])

{

    if (y == 3) return true;

    for (int i = x; i < m; i++){

        if (sum + a[i] <= l && c[i]){

            c[i] = 0, sum += a[i];

            if (sum == l){

                if (dfs(0, 0, y+1, l, m, a, c))

                    return true;

                else

                    c[i] = 1, sum -= a[i];

            }

            else if (dfs(sum, i+1, y, l, m, a, c))

                return true;

            else

                c[i] = 1, sum -= a[i];

        }

    }

    return false;

}

int main()

{

    int m, a[25], c[25], cas;

    scanf("%d", &cas);

    while (cas--){

        int sum = 0;

        scanf("%d", &m);

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

            scanf("%d",&a[i]), c[i] = 1, sum += a[i];

        sort(a, a+m);

        if (sum%4 || a[m-1] > sum/4)

            printf("no\n");

        else if (dfs(0, 0, 0, sum/4, m, a, c))

            printf("yes\n");

        else

            printf("no\n");

    }

}