The basic idea is to try each value in range `[1, N]`

at every possible position `1, 2, .. N`

. However, if simply brute force to go though all possible `N!`

permutations, you will get TLE since `15!`

is in huge magnitude of `10^12`

.

So the key is to skip a group of permutations as early as possible if they cannot form a *beautiful arrangement* at all.

**Trie "Construction":** (no need to actually contruct the trie)

Imagine all permutations form a trie

- The trie is rooted at a dummy level-
`0`

node which has`N`

level-`1`

child nodes:`1, 2, ...N`

; - Each level-
`L`

(`1<=L<=N`

) node has exactly`N-L`

child nodes; - Each node's value is distinct from any of its ancestor's value (i.e., permutation).

**Key Properties:**

- Each path from root to a leaf forms a permutation of
`[1, N]`

. - A path is a
*beautiful arrangement*iff level-`L`

node value`i`

satisfies condition`(i%L)*(L%i) == 0`

for all nodes on the path.

**Algorithm:**

The algorithm is simply to pre-order traverse the trie and:

- Skip a sub-tree if condition
`(i%L)*(L%i) == 0`

is violated at any point. - Increment final count
`count`

whenever reaches a leaf (i.e., level-`N`

).

Note: since `N <= 15`

, `int used`

is enough to be used as a bit array to record if value `i`

(i.e., `i`

-bit position of `used`

) in `[1, N]`

has been used in permutation.

```
int count = 0; // count of beautiful arrangement
int countArrangement(int N, int used = 0, int L = 1) {
for (int i = 1; max(i,L) <= N ; i++)
if ((used & 1<<i)+(i%L)*(L%i) == 0) countArrangement(N, used^(1<<i), L+1);
return count += (L > N);
}
```

Here is an improved version inspired by @dreamchase to eliminate unnecessary index check in the loop (which speeds up frm ~200ms to ~60ms):

```
int nums[16] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; // natural ascending order
int countArrangement(int N, int s = 1) { // s: start index to swap
for (int i = s; i <= N; i++)
if ((nums[i]%s)*(s%nums[i]) == 0)
swap(nums[i],nums[s]), countArrangement(N,s+1), swap(nums[i],nums[s]);
return nums[0] += (s>N); // nums[0] used as place holder for count
}
```