<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:
    int numSquarefulPerms(vector<int>& nums) {
        int n = nums.size();
        map<vector<int>, map<int, int>> dp[n+1];

        for (int a = 0; a < n; a++) {
            dp[1][{nums[a]}][nums[a]] = 1;
        }

        map<int, int> counts;

        for (int a = 0; a < n; a++) {
            counts[nums[a]]++;
        }

        map<int, unordered_set<int>> mymap;

        for (int a = 0; a < n-1; a++) {
            for (int b = a+1; b < n; b++) {
                int sum = nums[a] + nums[b];
                int rt = sqrt(sum);
                if (rt * rt == sum) {
                    mymap[nums[a]].insert(nums[b]);
                    mymap[nums[b]].insert(nums[a]);
                }
            }
        }

        for (int len = 2; len <= n; len++) {
            unordered_set<int> seen;
            auto& m = dp[len-1];
            for (int a = 0; a < n; a++) {
                if (seen.find(nums[a]) != seen.end()) continue;
                seen.insert(nums[a]);

                for (auto rn: mymap[nums[a]]) {
                    for (auto& it1: m) {
                        auto v = it1.first;

                        auto i1 = std::lower_bound(v.begin(), v.end(), nums[a]);
                        auto i2 = std::upper_bound(v.begin(), v.end(), nums[a]);
                        auto cnt = i2 - i1;

                        if (cnt == counts[nums[a]]) continue;

                        v.push_back(nums[a]);
                        sort(v.begin(), v.end());
                        dp[len][v][nums[a]] += it1.second[rn];
                    }
                }
            }
        }

        int ans = 0;

        auto& M = dp[n];

        for (auto& it: M) {
            for (auto& it2: it.second) {
                ans += it2.second;
            }
        }

        return ans;
    }
}; 
14800