Beautiful Arrangement
Medium · backtracking
A row has n seats, numbered 1 to n from left to right, and n guests wearing badges numbered 1 to n, one guest per number. Every guest sits in exactly one seat.
A seating is neat when, for every seat, the badge number divides the seat number or the seat number divides the badge number. (For example, badge 3 may sit in seats 1, 3, 6, 9 and so on, and badge 6 may sit in seats 1, 2, 3, 6, 12 and so on.)
Return how many different neat seatings there are.
Examples
Example 1
Input: n = 3
Output: 3
The neat seatings are [1, 2, 3], [2, 1, 3] and [3, 2, 1], listing the badge in seat 1, then seat 2, then seat 3.
Example 2
Input: n = 2
Output: 2
Both [1, 2] and [2, 1] are neat, because 1 divides everything.
Example 3
Input: n = 4
Output: 8
Eight of the 24 possible seatings are neat.
Constraints
- 1 <= n <= 15