# LeetCode 526. Beautiful Arrangement

## Description

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

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`

## Explanation

Use the backtracking approach to find all the combinations where each position meets nums[i] is divisible by i or i is divisible by nums[i] condition.

## Python Solution

``````class Solution:
def countArrangement(self, n: int) -> int:
numbers = [i for i in range(1, n + 1)]

results = []
visited = set()
self.helper(results, numbers, [], visited)

return len(results)

def helper(self, results, numbers, combination, visited):

if len(combination) == len(numbers):
results.append(list(combination))
return

for num in numbers:
if num in visited:
continue

if num % (len(combination) + 1) != 0 and (len(combination) + 1) % num != 0:
continue

combination.append(num)