จำนวนอาร์เรย์ Squareful ใน C++

คำอธิบายปัญหา

อาร์เรย์ A เรียกว่า Squareful ถ้าคู่ที่ติดกันทุกคู่ มีผลรวมเป็นกำลังสองสมบูรณ์ หาจำนวนการเรียงสับเปลี่ยน (permutation) ของ A ที่เป็น Squareful

ตัวอย่าง

A = [3,30,6] → Output: 2
Permutations: [3,6,30] และ [30,6,3]

แนวทางแก้ปัญหา: Backtracking + Pruning

1. ฟังก์ชัน isSqr(n): ตรวจสอบว่า n เป็นกำลังสองสมบูรณ์
2. Backtracking แบบสลับตำแหน่ง (swap-based permutation generation)
   • ที่ตำแหน่ง idx ลองสลับกับ i = idx..n-1
   • เงื่อนไข: idx==0 หรือ isSqr(a[idx-1] + a[i])
   • ใช้ set visited กันการเลือกค่าเดิมซ้ำที่ระดับ idx เดียวกัน
3. เมื่อ idx == n เพิ่ม count

รายละเอียดการ Pruning

• visited set ป้องกันการสร้าง permutation ซ้ำจากค่าที่เท่ากัน
• เช็คเงื่อนไข squareful ทีละคู่ขณะสร้าง (early termination)

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

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

class Solution {
    int count = 0;
    
    bool isSqr(lli n) {
        lli x = sqrt(n);
        return x*x == n;
    }
    
    void solve(vector<int>& a, int idx) {
        if(idx == a.size()) { count++; return; }
        unordered_set<int> visited;
        for(int i=idx; i