Участник:F.Nikitin/NumSquarefulPerms

Материал из DISCOPAL
Перейти к: навигация, поиск
import collections
 
def dfs(x, graph, count, todo):
    count[x] -= 1
    if todo == 0:
        ans = 1
    else:
        ans = 0
        for y in graph[x]:
            if count[y]:
                ans += dfs(y, graph, count, todo - 1)
    count[x] += 1
    return ans
 
class Solution:
    def numSquarefulPerms(self, A):
        count = collections.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)
        return sum(dfs(x, graph, count, len(A) - 1) for x in count)