<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:
    def numSquarefulPerms(self, nums: List[int]) -> int:
        bad = set()
        n = len(nums)
        for i in range(n):
            for j in range(i+1,n):
                x = nums[i]+nums[j]
                sx = floor(sqrt(x))
                if x != sx * sx:
                    bad.add((i, j))
                    bad.add((j, i))
        from functools import lru_cache
        @lru_cache(None)
        def dp(free, prev):
            if not free:
                return 1
            ans = 0
            m = free
            while m:
                bit = (m ^ (m-1)).bit_length() - 1
                if (bit, prev) not in bad:
                    ans += dp(free&~(1<<bit), bit)
                m -= 1<<bit
            return ans
        # def dfs(free, prev, idx):
        #     nonlocal cnt
        #     if idx == n:
        #         bit = free.bit_length() - 1
        #         if (bit, prev) not in bad:
        #             cnt += 1
        #         return
        #     m = free
        #     while m:
        #         bit = (m ^ (m-1)).bit_length() - 1
        #         if (bit, prev) not in bad:
        #             dfs(free&~(1<<bit),bit,idx+1)
        #         m -= 1<<bit                    
        if not bad:
            x = 1
            while n:
                x *= n
                n -= 1
            cnt = x
        else:
            cnt = dp((1<<n)-1,-1)

            # dfs((1<<n)-1,-1,1)
        # print(bad)
        from collections import Counter
        for x in Counter(nums).values():
            y = 1
            while x:
                y *= x
                x -= 1
            cnt //= y
        return cnt
18900