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

Source: leetcode | Difficulty: MEDIUM
Tags: Bit manipulation

Complete search

Dynamic programming

Mathematics

Data structures

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]) ** 0.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))
			elif 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) ** 0.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:
		candidates = collections.Counter(A)
		graph = {x: [y for y in candidates if int((x + y) ** 0.5) ** 2 == x + y] for x in candidates}
		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 = 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
		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:
		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 = [[0] * 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
				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


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]:
				continue
			dp[1 << i][i] = 1
		for s in range(1 << n):
			for i in range(n):
				if dp[s][i] <= 0:
					continue
				for j in range(n):
					if not g[i][j] or s & 1 << 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))


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

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

		@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
		for a in va:
			isValid = True
			for idx in range(1, len(a)):
				if (a[idx] + a[idx - 1]) ** 0.5 != int((a[idx] + a[idx - 1]) ** 0.5):
					isValid = False
					break
			if isValid:
				valid += 1
		return valid


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


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
		while i * i <= self.a[-1] * 2:
			self.square.add(i * i)
			i += 1
		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
			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
		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()
		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))