<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 is_perfect_square(self, n, m):
        l, r = 0, max(n,m) 

        while l < r:
            mid = l  + (r - l) // 2
            if mid * mid >= n + m:
                r = mid
            else:
                l = mid + 1
        return l * l == n + m

    def dfs(self, used, path):
        if len(path) == self.n:
            self.res.add(",".join(path))
        
        for i in range(self.n):
            if i > 0 and used[i - 1] == False and self.nums[i] == self.nums[i-1]:
                continue
            if used[i]:
                continue
            if path and not self.is_perfect_square(int(path[-1]), self.nums[i]):
                continue
            used[i] = True
            path.append(str(self.nums[i]))
            self.dfs(used, path)
            used[i] = False
            path.pop()
        
    def numSquarefulPerms(self, nums: List[int]) -> int:
        self.n = len(nums)
        self.nums = nums
        self.res = set()
        self.dfs([False] * self.n, [])
        return len(self.res)
        
16300