Beautiful Arrangement

Arrange every integer from 1 through n exactly once in positions 1 through n. An arrangement is beautiful when, at every position, either its value divides…

Arrange every integer from 1 through n exactly once in positions 1 through n. An arrangement is beautiful when, at every position, either its value divides the position or the position divides its value. Return the number of beautiful arrangements, not the arrangements themselves. Positions are one-based, and either divisibility direction is sufficient.

- n is an integer with 1 <= n <= 15; Boolean and coerced values are invalid. - Return one native integer count, not a Boolean, string or collection. - Every value from 1 through n is used exactly once.

Example 1: input n = 2; output 2. Both [1,2] and [2,1] satisfy the one-based divisibility rule.

Example 2: input n = 3; output 3. The valid arrangements are [1,2,3], [2,1,3] and [3,2,1].

Example 3: input n = 4; output 8. Eight permutations satisfy every position, even though 4! permutations exist in total.

Category: Recursion. Topic: recursion. Difficulty: Medium. Patterns: backtracking, bit-manipulation, dynamic-programming.