Problem :

https://leetcode.com/problems/number-of-squareful-arrays/


My Solution :

class Solution:
def numSquarefulPerms(self, A):
def is_squareful(n):
return int(n**0.5)**2 == n

def dfs(last, remain):
if remain == 0:
self.ans += 1
return
for num in counter:
if counter[num]:
if last == -1 or is_squareful(last + num):
counter[num] -= 1
dfs(num, remain-1)
counter[num] += 1

counter = {}
for num in A:
counter[num] = counter.get(num, 0) + 1
self.ans = 0
dfs(-1, len(A))
return self.ans


Comment :

비슷한 유형을 반복해서 풀다 보니 비슷한 풀이를 떠올리게 된다.

중복 원소가 존재하는 순열 문제


2019/08/18 - [프로그래밍/LeetCode] - [LeetCode][Python3] 47. Permutations II