Description

Submission

class Solution {
    vector<vector<int>> next;
    int visited[12];
    int n;
    int ret;
public:
    int numSquarefulPerms(vector<int>& A) {
        sort(A.begin(), A.end());
        n = A.size();
        next.resize(n);

        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                if(i == j) continue;
                if(sqrt(A[i] + A[j]) == (int)sqrt(A[i] + A[j])) {
                    next[i].push_back(j);
                }
            }
        }

        for(int i = 0; i < n; ++i) {
            if (i>0 && A[i]==A[i-1]) continue;
            visited[i] = 1;
            dfs(A, i, 1);
            visited[i] = 0;
        }

        return ret;
    }

    void dfs(vector<int>& A, int cur, int count) {
        if(count == n) {
            ret++;
            return;
        }
        int last = -1;
        for(auto i : next[cur]) {
            if(last == A[i]) continue;
            if(visited[i]) continue;
            visited[i] = 1;
            dfs(A, i, count+1);
            visited[i] = 0;
            last = A[i];
        }
    }
};