वर्गपूर्ण सरणियों की संख्या C++ में

मान लीजिए हमारे पास धनात्मक पूर्णांकों की एक सरणी A है, हम कह सकते हैं कि सरणी वर्गपूर्ण है यदि प्रत्येक आसन्न जोड़ी का योग एक पूर्ण वर्ग है। हमें A के उन क्रमपरिवर्तनों की संख्या ढूंढनी है जो वर्गपूर्ण हैं। दो क्रमपरिवर्तन A1 और A2 तभी अलग होंगे जब कुछ सूचकांक i ऐसा हो कि A1[i] != A2[i]।

उदाहरण के लिए, यदि इनपुट [3,30,6] है, तो आउटपुट 2 होगा, क्योंकि हमारे पास [3,6,30] और [30,6,3] जैसे दो क्रमपरिवर्तन हैं।

हल करने का दृष्टिकोण

हम बैकट्रैकिंग का उपयोग करते हैं जिसमें प्रूनिंग के लिए विज़िटेड सेट होता है:

जांचें कि क्या कोई संख्या पूर्ण वर्ग है: isSqr(n)
सरणी के सभी क्रमपरिवर्तन उत्पन्न करने के लिए पुनरावर्ती फ़ंक्शन solve(a, idx) परिभाषित करें
स्थिति idx पर, शेष सभी तत्वों को आजमाएं
केवल तभी रखें जब idx==0 या a[idx-1] + a[i] पूर्ण वर्ग हो
इस स्तर पर डुप्लिकेट से बचने के लिए विज़िटेड सेट का उपयोग करें
वैध क्रमपरिवर्तनों की गणना करें

उदाहरण

#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)); 
    return 0;
}

इनपुट

{3,30,6}