题意分析

给定一组木棒，判断是否能拼成一个正方形（所有木棒必须用完，且四条边长度相等）。

解题思路

1. 总长度必须能被$4$整除，否则无法构成正方形。
2. 目标边长$= \text{总长度} / 4$，若有木棒长度超过目标边长，直接排除。
3. DFS回溯+剪枝：尝试将木棒分配到$4$条边，若某条边超过目标长度则剪枝。

实现步骤

1. 计算总长度，检查是否能被$4$整除。
2. 降序排序木棒，优先尝试较长的木棒以提高剪枝效率。
3. DFS回溯：
   • 维护一个数组记录当前$4$条边的长度。
   • 尝试将每根木棒放入$4$条边之一，若某条边达到目标长度则递归处理下一条边。
   • 若当前边超过目标长度或剩余木棒无法满足剩余需求，则回溯。
4. 成功条件：$4$条边均恰好达到目标长度。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 回溯辅助函数
bool backtrack(const vector<int>& nums, vector<int>& sides, size_t index, int target) {
    if (index == nums.size()) {
        return sides[0] == target && sides[1] == target && 
               sides[2] == target && sides[3] == target;
    }
    
    for (int i = 0; i < 4; ++i) {
        // 剪枝条件：如果当前边和上一边长度相同，则跳过
        if (i > 0 && sides[i] == sides[i-1]) continue;
        
        if (sides[i] + nums[index] <= target) {
            sides[i] += nums[index];
            if (backtrack(nums, sides, index + 1, target)) return true;
            sides[i] -= nums[index];
        }
    }
    return false;
}

bool canFormSquare(vector<int>& nums) {
    if (nums.size() < 4) return false;
    
    int sum = 0;
    // 使用C++98兼容的for循环
    for (vector<int>::iterator it = nums.begin(); it != nums.end(); ++it) {
        sum += *it;
    }
    
    if (sum % 4 != 0) return false;
    
    int target = sum / 4;
    vector<int> sides(4, 0);
    
    // 降序排列以优化剪枝
    sort(nums.begin(), nums.end(), greater<int>());
    
    return backtrack(nums, sides, 0, target);
}

int main() {
    int N;
    cin >> N;
    
    for (int i = 0; i < N; ++i) {
        int M;
        cin >> M;
        
        vector<int> sticks(M);
        for (int j = 0; j < M; ++j) {
            cin >> sticks[j];
        }
        
        if (canFormSquare(sticks)) {
            cout << "yes" << endl;
        } else {
            cout << "no" << endl;
        }
    }
    
    return 0;
}