Matchsticks to Square จับไม้ขีดไฟเป็นสี่เหลี่ยมจัตุรัสใน C++

กำหนดความยาวไม้ขีดไฟหลายเส้น หาว่าจับเป็นสี่เหลี่ยมจัตุรัสได้ไหม (ใช้หมดทุกเส้น ห้ามหัก)

ตัวอย่าง: [1,1,2,2,2] → true (ด้านยาว 2: 1+1, 2, 2, 2)

วิธีแก้ปัญหา (Backtracking + Pruning)

1. ถ้าผลรวมไม่หาร 4 ลงตัว → false
2. target = sum/4, เรียงไม้จากใหญ่ไปเล็ก (pruning เร็วขึ้น)
3. DFS/Backtracking ใส่ไม้แต่ละเส้นลงใน 4 ด้าน:
   • ถ้าด้านใดเกิน target → skip
   • ใส่ไม้, เรียก recursive, ถ้าสำเร็จ → true
   • ถอนไม้กลับ (backtrack)
4. ถ้าใส่หมดทุกเส้นและ 3 ด้านแรก = target → true

ตัวอย่างโค้ด C++

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

class Solution {
public:
    bool solve(int idx, vector<int>& sums, int target, vector<int>& nums) {
        if (idx >= nums.size()) {
            return sums[0] == sums[1] && sums[1] == sums[2] && 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;
    }
    
    bool makesquare(vector<int>& nums) {
        if (nums.empty()) return false;
        int sum = 0;
        for (int x : nums) sum += x;
        if (sum % 4) return false;
        sort(nums.rbegin(), nums.rend());
        vector<int> sums(4);
        return solve(0, sums, sum / 4, nums);
    }
};

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

Input

[1,1,2,2,2]

Output

1