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

class Solution {
public:

    vector<int> cfg;

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

    void bt(int i, int& ans, const vector<int>& a, const map<int, int>& cnt) {
        int n = a.size();
        if (i == n) {
            // process cfg
            bool ok = true;
            for (int i = 0; i < n - 1; i++) {
                if (!checkSquare(cfg[i] + cfg[i + 1])) {
                    ok = false;
                    break;
                }
            }
            // for (auto e : cfg) cout << e << " ";
            // cout << "ok: " << ok << endl;
            if (ok) ans++;
            return;
        }

        map<int, int> cur_cnt;
        for (int j = 0; j < i; j++) {
            cur_cnt[cfg[j]]++;
        }

        for (auto p : cnt) {
            if (p.second == cur_cnt[p.first]) continue;
            if (i > 0 && !checkSquare(cfg[i - 1] + p.first)) continue;
            cfg.push_back(p.first);
            bt(i + 1, ans, a, cnt);
            cfg.pop_back();
        }

    }

    int numSquarefulPerms(vector<int>& a) {
        int ans = 0;
        sort(a.begin(), a.end());
        map<int, int> cnt;
        for (auto e : a) cnt[e]++;
        bt(0, ans, a, cnt);
        return ans;
    }
};
11800