# LeetCode 526: Beautiful Arrangement

## Problem Restatement

We are given an integer `n`.

There are `n` integers labeled from `1` to `n`.

We need to count how many permutations of these numbers are beautiful.

A permutation `perm` is beautiful if, for every position `i`, at least one of these is true:

```python
perm[i] % i == 0
```

or:

```python
i % perm[i] == 0
```

The permutation is 1-indexed. That means positions start from `1`, not `0`.

The problem asks us to return the number of beautiful arrangements.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer `n` |
| Output | The number of beautiful arrangements |
| Constraint | `1 <= n <= 15` |
| Rule | Each number from `1` to `n` must be used exactly once |

Example function shape:

```python
def countArrangement(n: int) -> int:
    ...
```

## Examples

For:

```python
n = 2
```

The numbers are:

```python
[1, 2]
```

There are two permutations.

First:

```python
[1, 2]
```

At position `1`, we have `1`.

```python
1 % 1 == 0
```

At position `2`, we have `2`.

```python
2 % 2 == 0
```

So `[1, 2]` is beautiful.

Second:

```python
[2, 1]
```

At position `1`, we have `2`.

```python
2 % 1 == 0
```

At position `2`, we have `1`.

```python
2 % 1 == 0
```

So `[2, 1]` is also beautiful.

Therefore:

```python
countArrangement(2) == 2
```

For:

```python
n = 1
```

There is only one permutation:

```python
[1]
```

It is beautiful, so the answer is:

```python
1
```

## First Thought: Brute Force

The direct solution is to generate every permutation of the numbers from `1` to `n`.

For each permutation, check every position.

If every position satisfies the divisibility rule, count it.

Pseudo-code:

```python
answer = 0

for perm in all_permutations([1, 2, ..., n]):
    valid = True

    for i in range(1, n + 1):
        if perm[i] % i != 0 and i % perm[i] != 0:
            valid = False
            break

    if valid:
        answer += 1
```

This works logically, but it wastes time.

It builds many permutations that fail early. For example, if position `2` already has a number that does not satisfy the rule, there is no reason to finish constructing the rest of that permutation.

## Problem With Brute Force

There are `n!` permutations.

When `n = 15`, `15!` is too large to enumerate directly.

So instead of generating all permutations and checking them later, we should build only valid partial arrangements.

This is a natural backtracking problem.

## Key Insight

At position `pos`, we only need to try numbers `num` that satisfy:

```python
num % pos == 0 or pos % num == 0
```

If a number does not satisfy this rule at the current position, placing it there can never lead to a valid arrangement.

So we prune that branch immediately.

The recursive idea is:

1. Fill position `1`.
2. Then fill position `2`.
3. Continue until position `n`.
4. Count one arrangement when all positions are filled.

We also need to remember which numbers have already been used.

## Algorithm

Use a recursive backtracking function:

```python
dfs(pos)
```

where `pos` is the current 1-indexed position we are trying to fill.

Maintain a boolean array:

```python
used[num]
```

where `used[num]` tells us whether `num` has already been placed in the arrangement.

At each position:

1. Try every number from `1` to `n`.
2. Skip numbers that are already used.
3. Check whether the number satisfies the divisibility rule.
4. If valid, mark it as used.
5. Recurse to the next position.
6. Unmark it after recursion.

When `pos == n + 1`, all positions have been filled, so we found one beautiful arrangement.

## Correctness

The algorithm tries to fill positions from `1` to `n`.

At every position `pos`, it only places a number `num` if `num` has not been used before. Therefore, every completed arrangement uses each number at most once.

Since the algorithm places exactly one number at each of the `n` positions, every completed arrangement uses exactly `n` numbers. Because all numbers come from `1` to `n` and no number is reused, every completed arrangement is a permutation of `1` through `n`.

The algorithm also checks the divisibility condition before placing a number. Therefore, every number placed at position `pos` satisfies:

```python
num % pos == 0 or pos % num == 0
```

So every completed arrangement counted by the algorithm is beautiful.

Now consider any valid beautiful arrangement. At position `1`, the algorithm will consider the number used by that arrangement. It passes the divisibility rule, so the recursion can choose it. The same is true for position `2`, then position `3`, and so on. Therefore, the algorithm has one recursive path that constructs this exact arrangement.

Thus, the algorithm counts every beautiful arrangement once and only once.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n!)` worst case | Backtracking may still explore many permutations |
| Space | `O(n)` | The recursion stack and `used` array both have size proportional to `n` |

The pruning makes the search much faster in practice than generating every permutation blindly.

The constraint `n <= 15` is small enough for this backtracking approach.

## Implementation

```python
class Solution:
    def countArrangement(self, n: int) -> int:
        used = [False] * (n + 1)

        def dfs(pos: int) -> int:
            if pos == n + 1:
                return 1

            count = 0

            for num in range(1, n + 1):
                if used[num]:
                    continue

                if num % pos == 0 or pos % num == 0:
                    used[num] = True
                    count += dfs(pos + 1)
                    used[num] = False

            return count

        return dfs(1)
```

## Code Explanation

We create a `used` array:

```python
used = [False] * (n + 1)
```

The array has size `n + 1` so that we can use numbers directly as indices.

For example, `used[3]` tells us whether number `3` has already been placed.

The recursive function is:

```python
def dfs(pos: int) -> int:
```

It returns the number of valid arrangements that can be formed starting from position `pos`.

The base case is:

```python
if pos == n + 1:
    return 1
```

If `pos` is `n + 1`, then positions `1` through `n` have already been filled. That means we found one complete beautiful arrangement.

Then we try every possible number:

```python
for num in range(1, n + 1):
```

If the number is already used, we skip it:

```python
if used[num]:
    continue
```

Otherwise, we check whether this number can be placed at the current position:

```python
if num % pos == 0 or pos % num == 0:
```

If it can, we mark it as used:

```python
used[num] = True
```

Then we count all arrangements that continue from the next position:

```python
count += dfs(pos + 1)
```

After the recursive call, we undo the choice:

```python
used[num] = False
```

This is the backtracking step. It allows the same number to be used in a different branch of the search.

Finally, we return the total count.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.countArrangement(1) == 1
    assert s.countArrangement(2) == 2
    assert s.countArrangement(3) == 3
    assert s.countArrangement(4) == 8
    assert s.countArrangement(5) == 10

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `n = 1` | Minimum input |
| `n = 2` | Matches the sample case |
| `n = 3` | Small enough to verify manually |
| `n = 4` | Checks deeper recursion |
| `n = 5` | Checks more branching |