Beautiful Arrangement

Problem Id: 526 Difficulty: Medium


Intuition

Solution


class Solution:
    def countArrangement(self, N: int) -> int:
        possibles = [[] for _ in range(N+2)]
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                if i % j == 0 or j % i == 0:
                    possibles[i].append(j)
        visited = [False] * (N + 1)
        return self.dfs(possibles, visited, 1)

    def dfs(self, possibles, visited, current):
        if current == len(visited):
            return 1
        ans = 0
        for nxt in possibles[current]:
            if not visited[nxt]:
                visited[nxt] = True
                ans += self.dfs(possibles, visited, current + 1)
                visited[nxt] = False
        return ans