Number of square arrays (day 81)

1： subject

 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  A  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 .

2： Code implementation

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

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 r * r == x;
}

void dfs(int u, int last)
{
    
    if (u == n) ans ++ ;
    else
    {
    
        for (int i = 0; i < n; i ++ )
        {
    
            if (st[i]) continue;  //  Used 
            if (i && !st[i - 1] && w[i] == w[i - 1])
                continue;
            if (!check(last + w[i])) continue;

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

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])
        {
    
            st[i] = true;
            dfs(1, w[i]);
            st[i] = false;
        }

    cout << ans << endl;
    return 0;
}