Số lượng mảng Squareful trong C++

Mảng A gọi là squareful nếu tổng của mỗi cặp phần tử liền kề là số chính phương. Tìm số hoán vị của A là squareful. Các hoán vị khác nhau nếu khác nhau tại ít nhất một vị trí.

Ví dụ: [3,30,6] → 2 hoán vị: [3,6,30] và [30,6,3].

Giải thuật

1. Hàm isSqr(n) kiểm tra n có phải số chính phương.
2. Backtracking với hàm solve(a, idx):
   • Nếu idx == size(a): tăng count, trả về.
   • Duyệt i từ idx đến n-1:
     • Nếu (idx == 0 HOẶC isSqr(a[idx-1] + a[i])) VÀ a[i] chưa dùng ở vị trí idx (tránh trùng lặp do giá trị giống nhau):
     • Hoán vị a[idx] và a[i].
     • Gọi solve(a, idx+1).
     • Hoán vị lại (backtrack).
     • Đánh dấu a[i] đã dùng tại vị trí idx.
3. Khởi tạo count = 0, gọi solve(A, 0), trả về count.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
    int count;
    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; }
        set<int> visited;
        for (int i = idx; i < a.size(); i++) {
            if ((idx == 0 || isSqr(a[idx-1] + a[i])) && !visited.count(a[i])) {
                swap(a[idx], a[i]);
                solve(a, idx+1);
                swap(a[idx], a[i]);
                visited.insert(a[i]);
            }
        }
    }
    int numSquarefulPerms(vector<int>& a){
        count = 0;
        solve(a, 0);
        return count;
    }
};
int main(){
    Solution ob;
    vector<int> v = {3,30,6};
    cout << (ob.numSquarefulPerms(v));
}

Đầu vào

{3,30,6}

Đầu ra

2