Given an array A of non-negative integers, the array is squareful if for every pair of adjacent elements, their sum is a perfect square.
Return the number of permutations of A that are squareful.  Two permutations A1 and A2 differ if and only if there is some index i such that A1[i] != A2[i].
Example 1:
Input: [1,17,8]
Output: 2
Explanation: 
[1,8,17] and [17,8,1] are the valid permutations.
Example 2:
Input: [2,2,2]
Output: 1
Note:
1 <= A.length <= 12
0 <= A[i] <= 1e9
class Solution:
    
    def dfs(self, pos):
        if pos==self.n:
            self.ans += 1
            return
        
        last = None
        for i, val in enumerate(self.a):
            if self.usable[i]:
                if val == last:
                    continue
                if pos-1 >= 0 and (val + self.rec[pos-1]) not in self.square:
                    continue
                
                self.usable[i] = False
                self.rec[pos] = val
                self.dfs(pos + 1)
                self.usable[i] = True
                last = val
    
    def numSquarefulPerms(self, A: List[int]) -> int:
        
        self.a = sorted(A)
        self.square=set()
        i = 0 # not 1
        while i*i <= self.a[-1]*2:
            self.square.add(i*i)
            i += 1
        
        #print(self.square)
        self.ans = 0
        self.n = len(self.a)       
        self.usable = [True]*self.n
        self.rec = [None]*self.n
        self.dfs(0)
        return self.ans
        
        
        

class Solution:
    
    def dfs(self, pos):
        if pos==self.n:
            self.ans += 1
            return
        
        last = None
        for i, val in enumerate(self.a):
            if self.usable[i]:
                if val == last:
                    continue
                if pos-1 >= 0 and (val + self.rec[pos-1]) not in self.square:
                    continue
                
                self.usable[i] = False
                self.rec[pos] = val
                self.dfs(pos + 1)
                self.usable[i] = True
                last = val
    
    def numSquarefulPerms(self, A: List[int]) -> int:
        
        self.a = sorted(A)
        self.square=set()
        i = 0 # not 1
        while i*i <= self.a[-1]*2:
            self.square.add(i*i)
            i += 1
        
        #print(self.square)
        self.ans = 0
        self.n = len(self.a)       
        self.usable = [True]*self.n
        self.rec = [None]*self.n
        self.dfs(0)
        return self.ans
        
        
        
