3063 小明爱正方形

小明很喜欢正方形，也喜欢火柴，现在小明有一些火柴，现在小明想知道用所有的火柴棒能不能拼成一个正方形。

输入

第一行一个数T，表示数据的组数(1≤T≤10)；
对于每组数据，
第一行输入一个数n，表示火柴的数目，其中1≤n≤15；
第二行n个数表示每根火柴的长度，其中火柴长度总和≤10^9。

输出

对于每组数据输出一行，
如果所有的火柴可以拼成正方形，输出true，否者输出false。

数据范围

对于25%的数据，1≤n≤8；
对于50%的数据，1≤n≤10；
对于100%的数据，1≤n≤15，1≤T≤10，每组火柴长度总和≤10^9；

输入样例

1
5
1 1 2 2 2

输出样例

true

样例解释

能拼成一个边长为2的正方形。

解析：

首先我们可以确定正方形的边长，对于最大值大于边长的或者sum%4不等于0或者火柴数目少于4的，都是false，接下来进行暴力dfs，这里是对于每一层把每根火柴忘每条边放置，判断条件是当前这条边边长小于等于sum/4,时间复杂度大约为O(4^15)。

放代码：

#include <iostream>
#include<bits/stdc++.h>
#include <algorithm>
using namespace std;
typedef long long ll;
int n;
ll a[15];
ll sum = 0;
bool used[15];
bool my_find(int x) {
    for (int i = n - 1; i >= 0; --i) {
        if (!used[i] && a[i] <= x) {
            if (a[i] == x) {
                used[i] = true;
                return true;
            }
            else {
                used[i] = true;
                bool flag = my_find(x - a[i]);
                if (flag) return true;
                used[i] = false;
            }
        }
    }
    return false;
}
int main(){
    int t;
    cin >> t;
    while (t--) {
        memset(used, false, sizeof(used));
        int cnt = 0; 
        sum = 0;
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            sum += a[i];
        }
        sort(a, a + n);
        if (sum % 4 != 0) {
            cout << "false" << endl;
            continue;
        }
        if (a[n - 1] > sum / 4) {
            cout << "false" << endl;
            continue;
        }
        bool flag = true;
        for (int i = n - 1; i >= 0; --i) {
            if (!used[i]) {
                used[i] = true;
                if (sum / 4 - a[i] == 0)continue;
                if (!my_find(sum / 4 - a[i])) {
                    flag = false;
                    break;
                }
            }
        }
        if (!flag) {
            cout << "false" << endl;
            continue;
        }
        else {
            bool f = true;
            for (int i = 0; i < n; ++i) {
                if (!used[i]) {
                    f = false;
                    break;
                }
            }
            if (f) cout << "true" << endl;
            else cout << "false" << endl;
        }
    }
    return 0;
}