# 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;
            }
        }
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/solutions/0526-beautiful-arrangement.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.