# 3-liner DFS with "Trie" perspective (detailed explanation with picture illustration)

• 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:

1. Each path from root to a leaf forms a permutation of `[1, N]`.
2. 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:

1. Skip a sub-tree if condition `(i%L)*(L%i) == 0` is violated at any point.
2. 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
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.