Beautiful Arrangement
Medium · Backtracking · about 20 minutes
Asked at Google, Amazon, Microsoft.
A permutation perm of 1..n (1-indexed) is beautiful if for every position i, perm[i] is divisible by i or i is divisible by perm[i]. Return the number of beautiful arrangements (n ≤ 15).