Solution using backtracking , using Bitmasking to keep track of visited element


#1
int cnt=0;
int isPerfect(int a){
    double x = sqrt(a);
    return (int)x*x == a;
}
void find(vector<int> &A, int ind, int mask, int prev){
    if(ind == A.size()) {
        cnt++;
        return;
    }
    unordered_set<int> s;
    for(int i = 0; i < A.size(); i++){
        if( ((mask >> i)&1) == 0 && s.count(A[i]) == 0){
            if(!ind || isPerfect(prev + A[i])){
                s.insert(A[i]);
                find(A, ind+1, (mask|(1 << i)), A[i]);
            }
            
        }
    }
    return;
}
int Solution::solve(vector<int> &A) {
        if(A.size() <= 1)
            return 0;
        cnt = 0;
        find(A, 0, 0, 0);
        return cnt;
}