P149 Square

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;

const int MAXN = 25;
int side;
int m;
int sticks[MAXN];
bool visit[MAXN];

bool cmp(int a, int b){
    return a > b;
}

bool DFS(int sum, int num, int position){
    if(num == 3){
        return true;
    }else{
        int sample = 0;  //剪枝 
        for(int i = position; i < m; ++i){  //遍历邻居节点 
            if(visit[i] || sum + sticks[i] > side || sticks[i] == sample){
                continue;
            }
            visit[i] = true; //标记该点 
            if(sum + sticks[i] == side){
                if(DFS(0, num + 1, 0)){
                    return true;
                }else{
                    sample = sticks[i];  //记录失败棍子长度 
                }
            }else{
                if(DFS(sum+sticks[i], num, i+1)){
                    return true;
                }else{
                    sample = sticks[i];  //记录失败棍子长度 
                }
            }
            visit[i] = false; //取消标记 
        }
        return false;
    }
}

int main(){
    int n, length;
    cin >> n;
    while(n--){
        cin >> m;
        length = 0;
        for(int i = 0; i < m; i++){
            cin >> sticks[i];
            length += sticks[i];
        }
        memset(visit, false, sizeof(visit));
        if(length % 4 != 0){   //剪枝 
            printf("no\n");
            continue;
        }
        sort(sticks, sticks + m, cmp); 
        side = length / 4;
        if(sticks[0] > side){  //剪枝 
            printf("no\n");
            continue;
        }
        if(DFS(0, 0, 0)){
            printf("yes\n");
        }else{
            printf("no\n");
        } 
    }
    return 0;
}