996. 正方形數組的數目
難度困難30
給定一個非負整數數組
A
,如果該數組每對相鄰元素之和是一個完全平方數,則稱這一數組為正方形數組。
傳回 A 的正方形排列的數目。兩個排列
A1
和
A2
不同的充要條件是存在某個索引
i
,使得 A1[i] != A2[i]。
示例 1:
輸入:[1,17,8]
輸出:2
解釋:
[1,8,17] 和 [17,8,1] 都是有效的排列。
示例 2:
輸入:[2,2,2]
輸出:1
提示:
-
1 <= A.length <= 12
-
0 <= A[i] <= 1e9
class Solution:
def numSquarefulPerms(self, A: List[int]) -> int:
self.res = 0
num = len(A)
if num == 0:
return 0
elif num == 1:
return 1 if math.sqrt(A[0]) % 1 == 0 else 0
# 給數組A從小到大排序
A.sort()
Visited = [False for _ in A]
def _judge(a : int, b : int) -> bool:
return True if math.sqrt(a + b) % 1 == 0 else False
def _trace_back(depth : int, path : List[int], Visited : List[bool]):
# 剪枝
if depth > 1 and not _judge(path[-1], path[-2]):
return
# 遞歸出口傳回結果
if depth == num:
self.res += 1
return
for i in range(num):
if not Visited[i]:
if i > 0 and A[i] == A[i - 1] and not Visited[i - 1]:
continue
Visited[i] = True
path.append(A[i])
_trace_back(depth + 1,path,Visited)
path.pop()
Visited[i] = False
_trace_back(0,[],Visited)
return self.res
心得體會