LeetCode Beautiful Arrangement Solution

Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n), either of the following is true:

  • perm[i] is divisible by i.
  • i is divisible by perm[i].

Given an integer n, return the number of the beautiful arrangements that you can construct.

Example 1:

Input: n = 2

Output: 2

Explanation:

The first beautiful arrangement is [1,2]: - perm[1] = 1 is divisible by i = 1 - perm[2] = 2 is divisible by i = 2 The second beautiful arrangement is [2,1]: - perm[1] = 2 is divisible by i = 1 - i = 2 is divisible by perm[2] = 1

Example 2:

Input: n = 1

Output: 1

Constraints:

  • 1 <= n <= 15

Problem Link: https://leetcode.com/problems/beautiful-arrangement/



Solution

Since this problem asks for the number of beautiful solutions, we will use the aggregation template for backtracking. We will fill in the logic.

  • additional state: unvisited to store unused numbers.
  • is_leaf: i == n+1, all the n numbers are used.
  • get_edges: all of the numbers from 1 to n
  • is_valid: not visited[num] and i % num == 0 or num % i == 0, check whether num is unused and num is beautiful for index i.

Implementation

1def countArrangement(self, n: int) -> int:
2    visited = [False] * (n+1)
3    def findBeautiful(i):
4        if i == n+1:
5            return 1
6        count = 0
7        for num in range(1, n+1):
8            if (not visited[num]) and (i % num == 0 or num % i == 0):
9                visited[num] = True
10                count += findBeautiful(i + 1)
11                visited[num] = False
12        return count
13    return findBeautiful(1)