C++-এ স্কোয়ারফুল অ্যারে পারমুটেশনের সংখ্যা

সমস্যা বিবরণ

একটি অ্যারে A দেওয়া থাকলে, সেটি স্কোয়ারফুল হবে যদি প্রতিটি সন্নিহিত জোড়ার যোগফল পারফেক্ট স্কোয়ার হয়। A-এর সকল পারমুটেশন 중 কতগুলো স্কোয়ারফুল তা বের করতে হবে।

উদাহরণ

A = [3,30,6] → আউটপুট = 2 (পারমুটেশন: [3,6,30] এবং [30,6,3])

সমাধান পদ্ধতি

• ব্যাকট্র্যাকিং (Backtracking) দিয়ে সব পারমুটেশন জেনারেট করা হয়।
• isSqr() ফাংশন দিয়ে পারফেক্ট স্কোয়ার চেক করা হয়।
• visited সেট দিয়ে ডুপ্লিকেট এড়ানো হয়।
• প্রতিটি স্টেপে বর্তমান এলিমেন্টের সাথে আগের এলিমেন্টের যোগফল চেক করা হয়।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;
typedef long long int 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;
        }
        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]);
            }
        }
    }
    
public:
    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);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: {3,30,6}

আউটপুট: 2