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

Difficulty: interview

Starter code:

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

Solutions:

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

        A.sort()
        self.ans = 0

        def check(A, i, path):
            return int((A[i] + path[-1])**0.5 + 0.0)**2 == A[i] + path[-1]

        def dfs(A, path):
            if not A:
                self.ans += 1
                return

            for i in range(len(A)):
                if i > 0 and A[i] == A[i - 1]:
                    continue
                if not path or (path and check(A, i, path)):
                    dfs(A[:i] + A[i + 1:], path + [A[i]])

        dfs(A, [])
        return self.ans


from copy import copy
class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        
        d = dict()
        count = dict()
        lim = len(A)
        blank = dict()
        for i in range(0,lim-1):  
            try:
                count[A[i]]+=1
            except:
                blank[A[i]]=0
                count[A[i]]=1
            for j in range(i+1,lim):
                if ((A[i]+A[j])**.5).is_integer():
                    try:
                        d[A[i]].add(A[j])
                    except:
                        d[A[i]] = set()
                        d[A[i]].add(A[j])
                    try:
                        d[A[j]].add(A[i])
                    except:
                        d[A[j]] = set()
                        d[A[j]].add(A[i])
        try:
            count[A[-1]]+=1
        except:
            count[A[-1]]=1
            blank[A[-1]]=0
            
        check = sorted(A)
        if d==dict():return 0
        f = set()
        c = 0
        def r(val,ld,l,lth):
            if lth==lim:
                f.add(tuple(l))
            else:
                if val in d:
                    for x in d[val]:
                        s = copy(ld)
                        if s[x]<=count[x]:
                            s[x]+=1
                            r(x,s,l+[x],lth+1)
        
        for x in set(A):
            r(x,blank,[x],1)
        for x in f:
            if sorted(list(x))==check:c+=1
        return c


class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        def get_valid():
            ans = 0
            seen = set()
            visited = set()
            while q:
                cur, remaining = q.popleft()
                if not remaining and cur not in seen:
                    ans += 1
                for i, n in enumerate(remaining):
                    sq = (cur[-1] + n) ** .5
                    if float(int(sq)) == sq:
                        add = cur + (n,)
                        remain = remaining[:i] + remaining[i+1:]
                        if (add, remain) not in visited:
                            q.append((add, remain))
                            visited.add((add, remain))
            return ans

        q = deque()
        for i, num in enumerate(A):
            q.append(((num, ), tuple(A[:i] + A[i+1:])))

        return get_valid()

class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        c = collections.Counter(A)
        cand = {i: {j for j in c if int((i + j)**0.5) ** 2 == i + j} for i in c}

        def dfs(x, left=len(A) - 1):
            c[x] -= 1
            count = sum(dfs(y, left - 1) for y in cand[x] if c[y]) if left else 1
            c[x] += 1
            return count
        return sum(map(dfs, c))

class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        ''' 
        # graph of indices, works if we don't have duplicate elements
        graph = collections.defaultdict(list)
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                if int((A[i]+A[j])**0.5)**2==(A[i]+A[j]):
                    graph[i] += [j]
                    graph[j] += [i]
        # source node
        graph[-1] = [i for i in range(len(A))]
        def dfs(node, visited):
            if len(visited)==len(A):
                return 1
            res = 0
            for neighbor in graph[node]:
                if neighbor in visited:
                    continue
                res += dfs(neighbor, visited|{neighbor})
            return res
        return dfs(-1, set())
        '''        
        candidates = collections.Counter(A)
        graph = {x: [y for y in candidates if int((x+y)**0.5)**2==x+y] for x in candidates}
        # source node
        graph[-1] = [x for x in candidates]
        def dfs(node, node_left):
            if node_left==0:
                return 1
            res = 0
            for n in graph[node]:
                if candidates[n]==0:
                    continue
                candidates[n] -= 1
                res += dfs(n, node_left-1)
                candidates[n] += 1
            return res
        return dfs(-1, len(A))

class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        #visited = [False] * len(A)
        
        visited = collections.Counter(A)
        
        ans = [0]
        self.calc(A, visited, [], ans)
        
        return ans[0]
    
    def calc(self, A, visited, tmp, ans):
        if len(tmp) == len(A):           
            ans[0] += 1
            #print(tmp)
            
        for i in list(visited.keys()):
            if visited[i] == 0:
                continue
                
            visited[i] -= 1
            tmp.append(i)
            
            if len(tmp) < 2 or (tmp[-1] + tmp[-2])**(0.5) == int((tmp[-1] + tmp[-2])**(0.5)):
                self.calc(A, visited, tmp, ans)
            
            tmp.pop()
            visited[i] += 1


class Solution:
    def numSquarefulPerms(self, nums: List[int]) -> int:
        #nums.sort()
        self.ans = 0
        
        def isSquare(v):
            x = int(v**0.5)
            return x * x == v
        
        def dfs(pos):
            
            if pos >= len(nums):
                self.ans += 1
                return
            
            used = set()
            for i in range(pos, len(nums)):
                if nums[i] in used:
                    continue
                used.add(nums[i])
                nums[pos], nums[i] = nums[i], nums[pos]
                
                if (pos == 0) or ( pos > 0 and isSquare(nums[pos] + nums[pos-1])):
                    dfs(pos+1)
                nums[pos], nums[i] = nums[i], nums[pos]
        dfs(0)
        return self.ans

class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        n = len(A)
        A = sorted(A)
        # g[i][j] = 1 if A[i], A[j] are squareful
        g = [[0] * n for _ in range(n)]
        # dp[s][i]: number of ways to reach state s and ends with node i
        dp = [[0] * n for _ in range(1 << n)]
        
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                r = int((A[i] + A[j]) ** 0.5)
                if r ** 2 == A[i] + A[j]:
                    g[i][j] = 1
                    
        for i in range(n):
            if i == 0 or A[i] != A[i - 1]:
                dp[(1 << i)][i] = 1
                
        ans = 0
        for s in range(1 << n):
            for i in range(n):
                if not dp[s][i]:
                    continue
                for j in range(n):
                    if not g[i][j]:
                        continue
                    if s & (1 << j):
                        continue
                    if j > 0 and not (s & (1 << (j - 1))) and A[j - 1] == A[j]:
                        continue
                    dp[s | (1 << j)][j] += dp[s][i]
                    
        for i in range(n):
            ans += dp[(1 << n) - 1][i]
        
        return ans


# https://zxi.mytechroad.com/blog/searching/leetcode-996-number-of-squareful-arrays/
# g[i][j]: if i and j are squareful
# dp[s][i]: # of ways to reach state s (binary mask of nodes visited) that ends with node i
# dp[s | (1 << j)][j] += dp[s][i] if g[i][j]
# 先对数组排序, 然后计算出所有的 g[i][j]
# for i in range(n) 初始化 dp[(1 << i)][i] = 1, 表示只有一个数字 i 的情况, 每个都是一种
# 如果有多个重复的数字, 只用第一个数字作为开头
# ans = sum(dp[(1 << n) - 1][i])
# O(n^2*2^n) time complexity, O(2^n) space complexity
import math
class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        n = len(A)
        A = sorted(A)
        g = [[False] * n for _ in range(n)]
        dp = [[0] * n for _ in range(1 << n)]
        
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                if int((A[i] + A[j]) ** 0.5 + 0.5) ** 2 == A[i] + A[j]:
                    g[i][j] = True

        for i in range(n):
            if i > 0 and A[i] == A[i - 1]:  # For the same numbers, only the first one can be the starting point
                continue
            dp[1 << i][i] = 1

        for s in range(1 << n):
            for i in range(n):
                if dp[s][i] <= 0:  # 如果 dp[s][i] <= 0, 说明没有以 i 结尾的情况, 跳过
                    continue
                for j in range(n):  # 尝试让任意一个数字连接在最后面
                    if not g[i][j] or (s & (1 << j)):  # 如果 i, j 不是 squareful 或 j 已经使用过, 跳过
                        continue
                    if j > 0 and not (s & (1 << (j - 1))) and A[j] == A[j - 1]:  # 出现重复的只使用第一个
                        continue
                    dp[s | (1 << j)][j] += dp[s][i]
        
        res = 0
        for i in range(n):
            res += dp[(1 << n) - 1][i]
        return res


import numpy as np
class Solution:
    graph = {}
    count = {}
    def numSquarefulPerms(self, A: List[int]) -> int:
        self.graph = {}
        self.count = {}
        for i in A:
            if i in self.count:
                self.count[i] += 1
            else:
                self.count[i] = 1
            self.graph[i] = []
            
        for i in self.count:
            for j in self.count:
                r = int(np.sqrt(i + j))
                if r * r == i + j:
                    self.graph[i].append(j)
        ans = 0
        L = len(A)
        for i in self.graph:
            ans += self.dfs(i, L-1)
        return ans
    
    def dfs(self, i, L):
        self.count[i] -= 1
        ans = 1
        if L != 0:
            ans = 0
            for j in self.graph[i]:
                if self.count[j] != 0:
                    ans += self.dfs(j, L - 1)
        self.count[i] += 1
        return ans
    


import numpy as np


class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        N = len(A)
        count = collections.Counter(A)
        graph = collections.defaultdict(list)
        for x in count:
            for y in count:
                if int((x + y) ** (0.5)) ** 2 == (x + y):
                    graph[x].append(y)
        
        def dfs(x, todo):
            count[x] -= 1
            if todo == 0:
                ans = 1
            else:
                ans = 0
                for y in graph[x]:
                    if count[y]:
                        ans += dfs(y, todo - 1)
                        
            count[x] += 1
            return ans
        
        return sum(dfs(x, N - 1) for x in count)

import numpy as np
class Solution:
    graph = {}
    count = {}
    def numSquarefulPerms(self, A: List[int]) -> int:
        self.graph = {}
        self.count = {}
        for i in A:
            if i in self.count:
                self.count[i] += 1
            else:
                self.count[i] = 1
            self.graph[i] = []
            
        for i in self.count:
            for j in self.count:
                r = int(np.sqrt(i + j))
                if r * r == i + j:
                    self.graph[i].append(j)
        ans = 0
        L = len(A)
        print((self.count))
        print((self.graph))
        for i in self.graph:
            ans += self.dfs(i, L-1)
        return ans
    
    def dfs(self, i, L):
        self.count[i] -= 1
        ans = 1
        if L != 0:
            ans = 0
            for j in self.graph[i]:
                if self.count[j] != 0:
                    ans += self.dfs(j, L - 1)
        self.count[i] += 1
        return ans
    


class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        def edge(x, y):
            return int((x + y) ** 0.5) ** 2 == (x + y)
        
        def dfs(x, t):
            count[x] -= 1
            if t == 0:
                ans = 1
            else:
                ans = 0
                for y in graph[x]:
                    if count[y]:
                        ans += dfs(y, t - 1)
            count[x] += 1
            return ans
                
        N = len(A)
        count = collections.Counter(A)
        graph = collections.defaultdict(list)
        for x in count:
            for y in count:
                if edge(x, y):
                    graph[x].append(y)
                    
        return sum(dfs(x, N - 1) for x in count)


from functools import lru_cache


class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        def edge(x, y):
            r = math.sqrt(x + y)
            return int(r) ** 2 == (x + y)
        
        @lru_cache(None)
        def dfs(node, seen):
            if seen == (1 << N) - 1:
                return 1
            
            ans = 0
            for n in graph[node]:
                nxt = seen | (1 << n)
                if nxt == seen:
                    continue
                ans += dfs(n, nxt)
            return ans
                    
        
        N = len(A)
        count = collections.Counter(A)
        graph = [[] for _ in range(N)]
        
        for i in range(N):
            for j in range(i + 1, N):
                if edge(A[i], A[j]):
                    graph[i].append(j)
                    graph[j].append(i)
                    
        ans = sum(dfs(i, 1 << i) for i in range(N))
        for v in count.values():
            ans //= math.factorial(v)
        
        return ans

class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        import math
        
        def is_not_square(num): 
            return int(math.sqrt(num) + 0.5) ** 2 != num
    
        memo = {}
        def perms(arr):
            key = tuple(sorted(arr))
            
            if key in memo: return memo[key]
            if len(arr) <= 1: return [arr]
            
            permutations = []
            seen = set()
            for i in range(len(arr)):
                el = arr[i]
                rest = arr[:i] + arr[i+1:]
                # if all([is_not_square(el+n) for n in rest]): continue
                if el not in seen:
                    sub_perms = perms(rest)
                    if not sub_perms: continue
                    for p in sub_perms:
                        if not is_not_square(el + p[0]):
                            permutations.append([el] + p)
                seen.add(arr[i])
                
            memo[key] = permutations
            return permutations
        
            
        return len(perms(A))
                


from functools import lru_cache

class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        N = len(A)
        
        def valid(x,y):
            return (math.sqrt(x+y)).is_integer()
        
        graph = [[] for _ in range(N)]
    
        for i,x in enumerate(A):
            for j in range(i):
                if valid(x,A[j]):
                    graph[i].append(j)
                    graph[j].append(i)
                    
        # FINDING NO OF HAMILTONIAN PATH
        
        @lru_cache(None)
        def dfs(node,visited):
            if visited == (1<<N) - 1:
                return 1
            
            ans = 0
            for val in graph[node]:
                if (visited & 1<<val)==0:
                    ans+= dfs(val,visited | 1<<val)
            return ans
        
        ans = sum(dfs(i,1<<i) for i in range(N))
        count = collections.Counter(A)
        for v in count.values():
            ans //= math.factorial(v)
        return ans

from functools import lru_cache

class Solution:
    def numSquarefulPerms(self, A):
        N = len(A)

        def edge(x, y):
            r = math.sqrt(x+y)
            return int(r + 0.5) ** 2 == x+y

        graph = [[] for _ in range(len(A))]
        for i, x in enumerate(A):
            for j in range(i):
                if edge(x, A[j]):
                    graph[i].append(j)
                    graph[j].append(i)

        # find num of hamiltonian paths in graph

        @lru_cache(None)
        def dfs(node, visited):
            if visited == (1 << N) - 1:
                return 1

            ans = 0
            for nei in graph[node]:
                if (visited >> nei) & 1 == 0:
                    ans += dfs(nei, visited | (1 << nei))
            return ans

        ans = sum(dfs(i, 1<<i) for i in range(N))
        count = collections.Counter(A)
        for v in count.values():
            ans //= math.factorial(v)
        return ans

from functools import lru_cache
class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        N = len(A)

        def edge(x, y):
            r = math.sqrt(x+y)
            return int(r + 0.5) ** 2 == x+y

        graph = [[] for _ in range(len(A))]
        for i, x in enumerate(A):
            for j in range(i):
                if edge(x, A[j]):
                    graph[i].append(j)
                    graph[j].append(i)

        # find num of hamiltonian paths in graph

        @lru_cache(None)
        def dfs(node, visited):
            if visited == (1 << N) - 1:
                return 1

            ans = 0
            for nei in graph[node]:
                if (visited >> nei) & 1 == 0:
                    ans += dfs(nei, visited | (1 << nei))
            return ans

        ans = sum(dfs(i, 1<<i) for i in range(N))
        count = collections.Counter(A)
        for v in count.values():
            ans //= math.factorial(v)
        return ans

class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        N = len(A)

        def edge(x, y):
            r = math.sqrt(x+y)
            return int(r + 0.5) ** 2 == x+y

        graph = [[] for _ in range(len(A))]
        for i, x in enumerate(A):
            for j in range(i):
                if edge(x, A[j]):
                    graph[i].append(j)
                    graph[j].append(i)

        # find num of hamiltonian paths in graph

        @lru_cache(None)
        def dfs(node, visited):
            if visited == (1 << N) - 1:
                return 1

            ans = 0
            for nei in graph[node]:
                if (visited >> nei) & 1 == 0:
                    ans += dfs(nei, visited | (1 << nei))
            return ans

        ans = sum(dfs(i, 1<<i) for i in range(N))
        count = collections.Counter(A)
        for v in count.values():
            ans //= math.factorial(v)
        return ans




def getPermutations(array):
    ans = set()
    def helper(arr,i,ans):
        if i==len(arr)-1:

            ans.add(tuple(arr))
            return
        
        for j in range(i,len(arr)):
            if not (arr[i]==arr[j] and i!=j):
                test = (i<=1) or (((arr[i-1]+arr[i-2])**0.5)==int((arr[i-1]+arr[i-2])**0.5))
                swap(arr,i,j)
                if (test):
                    helper(arr,i+1,ans)
            
                swap(arr,i,j)
            
    def swap(arr,i,j):
        arr[i],arr[j]=arr[j],arr[i]
        
    helper(array,0,ans)
    return ans

class Solution:
    
    
    
    def numSquarefulPerms(self, A: List[int]) -> int:
        va = getPermutations(A)
        
        valid = 0
        # print(va)
        for a in va:
            isValid = True
            # print(a)
            for idx in range(1,len(a)):
                
                if ((a[idx]+a[idx-1])**0.5)!=int((a[idx]+a[idx-1])**0.5):
                    # print(a,idx)
                    isValid = False
                    break
                    
            if isValid:
                # print(a)
                valid+=1
                
        # print(valid)
        return valid
        


from functools import lru_cache

class Solution:
    def numSquarefulPerms(self, A):
        N = len(A)

        def edge(x, y):
            r = math.sqrt(x+y)
            return int(r + 0.5) ** 2 == x+y

        graph = [[] for _ in range(len(A))]
        for i, x in enumerate(A):
            for j in range(i):
                if edge(x, A[j]):
                    graph[i].append(j)
                    graph[j].append(i)

        # find num of hamiltonian paths in graph
        @lru_cache(None)
        def dfs(node, visited):
            if visited == (1 << N) - 1:
                return 1
            ans = 0
            for nei in graph[node]:
                if (visited >> nei) & 1 == 0:
                    ans += dfs(nei, visited | (1 << nei))
            return ans

        ans = sum(dfs(i, 1<<i) for i in range(N))
        count = collections.Counter(A)
        for v in count.values():
            ans //= math.factorial(v)
        return ans

class Solution:
    def numSquarefulPerms(self, A):
        A.sort()
        N = len(A)
        graph = [[0] * N for _ in range(N)]

        for i in range(N):
            for j in range(N):
                if i==j: continue
                if int((A[i]+A[j])**0.5)**2==(A[i]+A[j]):
                    graph[i][j]=1
                    graph[j][i]=1


        dp=[[0]*N for i in range(1<<N)]
        for i in range(N):
            dp[1<<i][i]=1
        for s in range(1<<N):
            for i in range(N):
                if not dp[s][i]: continue
                for j in range(N):
                    if not graph[i][j]: continue
                    if s&(1<<j): continue
                    if j>0 and s&(1<<(j-1)) and A[j]==A[j-1]:continue
                    dp[s|(1<<j)][j]+=dp[s][i]

        ans=0
        for i in range(N):
            ans+=dp[-1][i]

        return ans
        

        


from collections import Counter

class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        
        counts = Counter(A)
        graph = {x: [] for x in counts}
        
        for x in counts:
            for y in counts:
                r = int((x + y) ** 0.5 + 0.5)
                if r * r == x + y:
                    graph[x].append(y)
                    
        def dfs(x, todo):
            counts[x] -= 1
            if todo == 0:
                res = 1
            else:
                res = 0
                for y in graph[x]:
                    if counts[y] > 0:
                        res += dfs(y, todo - 1)

            counts[x] += 1
            return res
            
            
        return sum(dfs(x, len(A) - 1) for x in counts)

from collections import Counter
from functools import lru_cache
import math

class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        # Backtracking
        # Time  complexity: O(N^N)
        # Space complexity: O(N)
        # N = len(A)
        # count = Counter(A)

        # graph = {x: [] for x in count}
        # for x in count:
        #     for y in count:
        #         if int((x + y) ** .5 + 0.5) ** 2 == x + y:
        #             graph[x].append(y)

        # def dfs(x, todo):
        #     count[x] -= 1
        #     if todo == 0:
        #         ans = 1
        #     else:
        #         ans = 0
        #         for y in graph[x]:
        #             if count[y]:
        #                 ans += dfs(y, todo - 1)

        #     count[x] += 1
        #     return ans

        # return sum(dfs(x, len(A) - 1) for x in count)


        # Dynamic Programming
        # Time  complexity: O(N^2 x 2^N) = O(sum_{k=1}^{N} C_N^K x C_k^2)
        # Space complexity: O(N x 2^N)
        N = len(A)

        def edge(x, y):
            r = math.sqrt(x + y)
            return int(r + 0.5) ** 2 == x + y

        graph = [[] for _ in range(len(A))]
        for i, x in enumerate(A):
            for j in range(i):
                if edge(x, A[j]):
                    graph[i].append(j)
                    graph[j].append(i)

        # find num of hamiltonian paths in graph
        @lru_cache(None)
        def dfs(node, visited):
            if visited == (1 << N) - 1:
                return 1

            ans = 0
            for nei in graph[node]:
                if (visited >> nei) & 1 == 0:
                    ans += dfs(nei, visited | 1 << nei)
            return ans

        ans = sum(dfs(i, 1 << i) for i in range(N))
        count = Counter(A)
        for v in list(count.values()):
            ans //= math.factorial(v)
        return ans


        # c = Counter(A)
        # cand = {i: {j for j in c if int((i+j)**.5) ** 2 == i + j} for i in c}
        # self.res = 0

        # def dfs(x, left=len(A)-1):
        #     c[x] -= 1
        #     if left == 0:
        #         self.res += 1
        #     for y in cand[x]:
        #         if c[y]:
        #             dfs(y, left - 1)
        #     c[x] += 1

        # for x in c: dfs(x)
        # return self.res


        # def backtrack(i, A):
        #     if i > 1:
        #         val = A[i - 2] + A[i - 1]
        #         is_square = math.sqrt(val) == math.floor(math.sqrt(val))
        #         if not is_square:
        #             return

        #     if i == len(A):
        #         output.append(A)
        #         return

        #     for j in range(i, len(A)):
        #         A[i], A[j] = A[j], A[i]
        #         search = (i, A[i], tuple(A[:i]))
        #         if search not in seen:
        #             seen.add(search)
        #             backtrack(i + 1, A)

        #         A[i], A[j] = A[j], A[i]

        # output, seen = [], set()
        # backtrack(0, A)
        # return len(output)



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 numSquarefulPerms(self, A: List[int]) -> int:
        
        d = defaultdict(int)
        res = 0
        
        ps = {}
        i = 0
        while i*i <= 2*max(A):
            ps[i*i]=True
            i += 1
            
        def ok(x):
            return x in ps
        
        def solve(x):
            nonlocal res
            # takes some number X and multiset D. Returns answer of the problem for numbers in D such that first number is X
            if not len(d):
                res += 1
                return
            for k in list(d.keys()):
                if not ok(x + k): continue
                d[k] -= 1
                if d[k] == 0: del d[k]
                solve(k)
                d[k] += 1
                
            
        for x in A: d[x] += 1
        for k in list(d.keys()):
            d[k] -= 1
            if not d[k]: del d[k]
            solve(k)
            d[k] += 1
            
        return res
                    


from typing import List
from collections import defaultdict

class Solution:
    def helper(self, last_num, used, partners, index):
        if index == len(used):
            return 1
        total = 0
        # print(partners, partners[last_num])
        for partner, partner_list in partners[last_num].items():
            for partner_index in partner_list:
                if not used[partner_index]:
                    used[partner_index] = True
                    total += self.helper(partner, used, partners, index+1)
                    used[partner_index] = False
                    break
        return total

    def numSquarefulPerms(self, A: List[int]) -> int:
        squares = set()
        i = 0
        partners = defaultdict(lambda: defaultdict(set))
        while i * i <= 200000000:
            squares.add(i*i)
            i += 1
        for i in range(len(A)):
            for j in range(i+1, len(A), 1):
                if A[i] + A[j] in squares:
                    partners[A[i]][A[j]].add(j)
                    partners[A[j]][A[i]].add(i)
        unique_nums = dict()
        for i, num in enumerate(A):
            unique_nums[num] = i
        used = [False for _ in A]
        total = 0
        for num, i in unique_nums.items():
            used[i] = True
            total += self.helper(num, used, partners, 1)
            used[i] = False
        return total

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

        A.sort()
        self.ans = 0

        def check(A, i, path):
            return int((A[i] + path[-1])**0.5 + 0.0)**2 == A[i] + path[-1]

        def dfs(A, path):
            if len(A) == 0:
                self.ans += 1
                return

            for i in range(len(A)):
                if i > 0 and A[i] == A[i - 1]:
                    continue
                if len(path) == 0 or (len(path) > 0 and check(A, i, path)):
                    dfs(A[:i] + A[i + 1:], path + [A[i]])

        dfs(A, [])
        return self.ans


class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        def edge(x, y):
            return int((x + y) ** 0.5) ** 2 == (x + y)
        
        def dfs(x, t):
            count[x] -= 1
            if t == 0:
                ans = 1
            else:
                ans = 0
                for y in graph[x]:
                    if count[y]:
                        ans += dfs(y, t - 1)
            count[x] += 1
            return ans
                    
        N = len(A)
        count = collections.Counter(A)
        graph = collections.defaultdict(list)
        for x in count:
            for y in count:
                if edge(x, y):
                    graph[x].append(y)
                    
        return sum(dfs(x, N - 1) for x in count)
                    
        
    
    
        


class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        A.sort()
        n = len(A)
        visited = [False] * n
        res = []
        self.count = 0
        def dfs(curr):
            if len(curr) == n:
                self.count += 1
                return 
            for i in range(n):
                if visited[i]: continue 
                if i > 0 and A[i] == A[i - 1] and not visited[i - 1]: continue 
                if len(curr) > 0 and (int((curr[-1] +  A[i]) ** 0.5))**2 != curr[-1] +  A[i]: continue 
                visited[i] = True
                dfs(curr + [A[i]])
                visited[i] = False
        dfs([])
        return self.count


from math import sqrt
class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        return self.backtrack(A, 0, set())
    
    def isPerfect(self, num):
        return int(sqrt(num))**2 == num
        
    def backtrack(self, permutation, j, seen):
        permutation_tuple = (j,) + tuple(permutation)
        if permutation_tuple in seen: return 0
        seen.add(permutation_tuple)
        if j == len(permutation):
            return 1
        total = 0
        for i in range(j, len(permutation)):
            self.swap(permutation, i, j)
            if j == 0 or self.isPerfect(permutation[j] + permutation[j-1]):
                total += self.backtrack(permutation, j+1, seen)
            self.swap(permutation, i, j)
        return total
    
    def swap(self, array, i, j):
        array[i], array[j] = array[j], array[i]


class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        count ={}
        for i in A:
            count[i]=count.get(i,0)+1
        graph = {x: [] for x in A}
        for x in count:
            for y in count:
                if int((x + y) ** 0.5 + 0.5) ** 2 == x + y:
                    graph[x].append(y)
        def dfs(x, todo):
            count[x] -= 1
            if todo == 0:
                ans = 1
            else:
                ans = 0
                for y in graph[x]:
                    if count[y]:
                        ans += dfs(y, todo - 1)
            count[x] += 1
            return ans

        return sum(dfs(x, len(A) - 1) for x in count)


class Solution:
    def numSquarefulPerms(self, A: List[int]) -> int:
        c = {}
        for i in A:
            c[i]=c.get(i,0)+1
        cand = {i: [j for j in c if int((i + j)**0.5) ** 2 == i + j] for i in c}

        def dfs(x, left=len(A) - 1):
            c[x] -= 1
            count = sum(dfs(y, left - 1) for y in cand[x] if c[y]) if left else 1
            c[x] += 1
            return count
        return sum(map(dfs, c))