[LeetCode][Python3] 996. Number of Squareful Arrays

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