How do you approach Beautiful Arrangement?

Fill positions 1..n, choosing an unused number that satisfies the divisibility rule.

What are common mistakes on Beautiful Arrangement?

Pushing the working array into the results without copying it, so every entry aliases the same array. Forgetting to undo the choice after the recursive call returns. Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

← Back to problems

Beautiful Arrangement

MediumAlgorithms

Description

Suppose you have `n` integers labeled `1` through `n`. A permutation `perm` (1-indexed) is **beautiful** if for every position `i`, either `perm[i]` is divisible by `i` or `i` is divisible by `perm[i]`. Return the number of beautiful arrangements you can construct.

Example 1

Input: n = 2

Output: 2

Explanation: [1,2] and [2,1] are both beautiful.

Constraints

- 1 <= n <= 15

Beautiful Arrangement: approach, complexity and pitfalls

A medium backtracking problem, graded against 4 test cases (2 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

More Backtrackingproblems →

If you are stuck

Show the 2-step hint ladder

Fill positions 1..n, choosing an unused number that satisfies the divisibility rule.
Backtrack and count whenever you successfully fill all positions.

The optimal approach

Show the approach: The approach

Position-by-position backtracking. For each position `pos`, try each unused number `num` where `num % pos === 0` or `pos % num === 0`, mark it used, and recurse. Count every full arrangement.

Time: O(k) where k is the number of valid arrangements (heavily pruned). Space: O(n).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.