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

from math import sqrt

class Solution:
    def numSquarefulPerms(self, nums: List[int]) -> int:
        
        def is_num_square(num):
            return int(num**0.5) == num**0.5

        n = len(nums)
        self.ans = 0
        cnt = Counter(nums)

        def bt():
            if len(tmp) == n:
                self.ans += 1

            for key in cnt:
                if cnt[key] and (not tmp or is_num_square(tmp[-1]+key)):
                    tmp.append(key)
                    cnt[key] -= 1
                    bt()
                    cnt[key] += 1
                    tmp.pop()

        tmp = []
        bt()

        return self.ans


'''
class Solution:
    def numSquarefulPerms(self, nums: List[int]) -> int:

        n = len(nums)
        ans = 0
        full_mask = pow(2,n) -1

        def ps(n):
            root = isqrt(n)
            return root * root == n
        
        def go(mask):
            nonlocal ans
            if mask == full_mask:
                ans += 1
                return

            for i in range(n):
                if mask & (1 << i):
                    continue
                # prevent duplicates
                if i > 0 and nums[i] == nums[i-1] and mask & (1 << i-1) == 0:
                    continue
                if prev == None or ps(nums[prev] + nums[i]):
                    go(mask | (1 << i))


        nums.sort()
        go(0)
        return ans
        '''
16800