398. Beautiful Arrangement
You receive a single integer n. Consider arranging the numbers 1 through n (each used exactly once) into positions 1 through n. Call an arrangement beautiful when every position i (1-indexed) holds a value perm[i] that is divisibility-compatible with its slot: either perm[i] divides i, or i divides perm[i].
Return the number of beautiful arrangements that exist for the given n.
For example, with n = 2 the arrangement [2, 1] is beautiful because position 1 divides everything and 1 divides position 2.
Example 1:
Input: n = 2
Output: 2
Explanation: Both orderings work. [1, 2]: 1 divides 1, and 2 is divisible by 2. [2, 1]: 2 is divisible by position 1, and 1 divides position 2.
Example 2:
Input: n = 4
Output: 8
Explanation: Of the 24 orderings of [1, 2, 3, 4], exactly 8 satisfy the divisibility rule at every position, e.g. [2, 1, 3, 4] and [4, 2, 3, 1].
Constraints:
- 1 ≤ n ≤ 15
Hints:
Trying all n! orderings and checking each one at the end wastes work — if position 1 already breaks the rule, no completion of that ordering can be beautiful. Place values one position at a time and abandon a partial arrangement the moment a placement is invalid.
With n <= 15, the set of already-used values fits in a 15-bit integer. Two different orders of placement that used the same set of values face the identical remaining subproblem — memoize on the bitmask so each of the 2^n states is solved once.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 2
Expected output: 2