184. Beautiful Arrangement

Medium · Backtracking

A beautiful arrangement is a permutation of the numbers 1 to n where, for every position i (counting from 1), either the number at that position divides i, or i divides that number. Given an integer n (1 ≤ n ≤ 15), count how many beautiful arrangements exist. For example, with n=2, both [1,2] and [2,1] are beautiful: in [1,2], position 1 has 1 (1 divides 1) and position 2 has 2 (2 divides 2); in [2,1], position 1 has 2 (2 divides 1 is false, but 1 divides 2 is true) and position 2 has 1 (1 divides 2). Input: a single integer n. Output: the count of valid permutations.

Examples

Example 1
Input: 1
Output: 1
Explanation: Only one permutation; trivially satisfies the rule
Example 2
Input: 2
Output: 2
Explanation: [1,2] and [2,1] both work

Constraints