# 0526. Beautiful Arrangement

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

## Description

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`

## ac

```java
class Solution {
    int res = 0;
    boolean[] visiting;

    public int countArrangement(int N) {
        // edge cases

        visiting = new boolean[N+1];
        backtrack(1, N);

        return res;
    }

    private void backtrack(int kth, int n) {
        // exit
        if (kth == n + 1) {
            res++;
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (visiting[i]) continue;
            if (i % kth == 0 || kth % i == 0) {
                visiting[i] = true;
                backtrack(kth+1, n);
                visiting[i] = false;
            }
        }
    }
}
```

same code, slight change. starting from backward accelerate the process because it avoids entering wrong path in earlier stage.

```java
class Solution {
    int res = 0;
    boolean[] visiting;

    public int countArrangement(int N) {
        // edge cases

        visiting = new boolean[N+1];
        backtrack(N, N);

        return res;
    }

    private void backtrack(int kth, int n) {
        // exit
        if (kth == 0) {
            res++;
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (visiting[i]) continue;
            if (i % kth == 0 || kth % i == 0) {
                visiting[i] = true;
                backtrack(kth-1, n);
                visiting[i] = false;
            }
        }
    }
}
```
