<p>An array is <strong>squareful</strong> if the sum of every pair of adjacent elements is a <strong>perfect square</strong>.</p>

<p>Given an integer array nums, return <em>the number of permutations of </em><code>nums</code><em> that are <strong>squareful</strong></em>.</p>

<p>Two permutations <code>perm1</code> and <code>perm2</code> are different if there is some index <code>i</code> such that <code>perm1[i] != perm2[i]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,17,8]
<strong>Output:</strong> 2
<strong>Explanation:</strong> [1,8,17] and [17,8,1] are the valid permutations.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,2,2]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 12</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

using A = array<int, 6>;

void nxt(int& x) {
    int c = x & -x, r = x + c;
    x = (((x ^ r) >> 2) / c) | r;
}

int sq(int x) {
    int y = int(sqrt(x));
    return y * y == x;
}

class Solution {
  public:
    int numSquarefulPerms(vector<int>& nums) {
        int n = size(nums);
        if (n == 1) return 1;
        sort(begin(nums), end(nums));
        int ans = 0;
        A l, r;
        set<A> lh, rh;
        for (int s = (1 << n / 2) - 1; s < 1 << n; nxt(s)) {
            l = r = {};
            for (int i = 0, li = 0, ri = 0; i < n; i++)
                (s >> i & 1 ? l[li++] : r[ri++]) = nums[i];
            if (auto lit = lh.find(l), rit = rh.find(r);
                lit == end(lh) && rit == end(rh))
                lh.insert(lit, l), rh.insert(rit, r);
            else
                continue;
            map<int, int> lc, rc;
            do {
                int ok = 1;
                for (int i = 1; ok && i < n / 2; i++) ok &= sq(l[i - 1] + l[i]);
                if (ok) lc[l[n / 2 - 1]]++;
            } while (next_permutation(begin(l), begin(l) + n / 2));
            do {
                int ok = 1;
                for (int i = 1; ok && i < n - n / 2; i++)
                    ok &= sq(r[i - 1] + r[i]);
                if (ok) rc[r[0]]++;
            } while (next_permutation(begin(r), begin(r) + (n - n / 2)));
            for (auto [x, c] : lc)
                for (auto [y, d] : rc)
                    if (sq(x + y)) ans += c * d;
        }
        return ans;
    }
};
10900