Ghép que diêm thành vuông (Matchsticks to Square) trong C++

Cho các que diêm độ dài khác nhau, xác định có thể ghép thành hình vuông dùng hết que không (không gãy que).

Ví dụ: [1,1,2,2,2] → true (cạnh 2, một cạnh dùng 2 que 1).

Thuật toán (Backtracking + Pruning)

1. Tổng độ dài phải chia hết cho 4. Mục tiêu mỗi cạnh = sum/4.
2. Sắp xếp que giảm dần (cắt tỉa sớm).
3. DFS gán que vào 4 cạnh, nếu cạnh nào vượt mục tiêu → bỏ qua.
4. Khi gán hết que, kiểm tra 3 cạnh đầu = mục tiêu (cạnh 4 tự động đúng).

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    bool solve(int idx, vector& sums, int target, vector& nums) {
        if (idx >= nums.size()) 
            return sums[0]==target && sums[1]==target && sums[2]==target;
        for (int i=0; i<4; i++) {
            if (sums[i] + nums[idx] > target) continue;
            sums[i] += nums[idx];
            if (solve(idx+1, sums, target, nums)) return true;
            sums[i] -= nums[idx];
        }
        return false;
    }
public:
    bool makesquare(vector& nums) {
        if (nums.empty()) return false;
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 4) return false;
        sort(nums.rbegin(), nums.rend());
        vector sums(4,0);
        return solve(0, sums, sum/4, nums);
    }
};

int main() {
    vector v = {1,1,2,2,2};
    Solution ob;
    cout << ob.makesquare(v); // 1 (true)
    return 0;
}

Đầu vào / Đầu ra

Input: [1,1,2,2,2]

Output: 1