4519. Number of square arrays

Given an array of nonnegative integers A, If the sum of each pair of adjacent elements in the array is a complete square , This array is called a square array .

return A The number of squares arranged by .

Two permutations A1 and A2 Different if and only if there is an index i, bring A1[i]≠A2[i].

Input format

The first line contains an integer n, Represents an array AA The length of .

The second line contains n It's an integer A[i].

Output format

An integer , Express A The number of squares arranged by .

Data range

1≤n≤12,
0≤A[i]≤109.

sample input ：

3
1 17 8

sample output ：

2

Sample explanation

[1,8,17] and [17,8,1] They're all effective permutations .

Code ：

//  Pay attention to the skills of weight judgment   Special treatment of equal values 
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int n;
int w[N];
bool st[N];
int ans;

bool check(int x)
{
    
    int r = sqrt(x);
    return x == r * r;
}

void dfs(int u, int last)
{
    
    if (u == n)
    {
    
        ans++;
        return;
    }

    for (int i = 0; i < n; i++)
    {
    
        if (st[i])
            continue;
        if (i && !st[i - 1] && w[i] == w[i - 1]) //  If the previous one has not been accessed and is equal to the current value   It indicates that the previous one has been searched and unmarked   Then the current one does not need to be searched 
            continue;
        if (!check(w[i] + last))
            continue;

        st[i] = 1;
        dfs(u + 1, w[i]);
        st[i] = 0;
    }
}

int main()
{
    
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> w[i];
    sort(w, w + n);

    for (int i = 0; i < n; i++)
    {
    
        if (!i || w[i] != w[i - 1]) //  Prevent permutations with the same results 
        {
    
            st[i] = true;
            dfs(1, w[i]);
            st[i] = 0;
        }
    }

    cout << ans << endl;

    return 0;
}