Beautiful Arrangement: Backtracking with Divisibility Pruning
Given an integer n, return the number of beautiful arrangements you can construct. A permutation perm of [1, 2, ..., n] is called a beautiful arrangement if for every position i (1-indexed), either perm[i] is divisible by i, or i is divisible by perm[i].
This is LeetCode 526: Beautiful Arrangement, and it is a clean example of how backtracking with pruning can solve a constrained permutation problem efficiently. Instead of generating all n! permutations and filtering, you check the divisibility constraint as you place each number, cutting off invalid branches before they grow.
The problem
You are given an integer n between 1 and 15. You need to count how many permutations of [1, 2, ..., n] satisfy the "beautiful" condition: for every 1-indexed position i, either perm[i] % i == 0 or i % perm[i] == 0.
For n = 2, the two permutations are [1, 2] and [2, 1]. Both are beautiful. [1, 2]: position 1 has 1 (1 % 1 = 0), position 2 has 2 (2 % 2 = 0). [2, 1]: position 1 has 2 (2 % 1 = 0), position 2 has 1 (2 % 1 = 0). Answer: 2.
For n = 3, only three of the six permutations satisfy the condition: [1, 2, 3], [2, 1, 3], and [3, 2, 1]. The other three all fail because some number lands in a position where neither divisibility direction holds.
The key insight
You do not need to build all permutations and then check. You can check the divisibility constraint at each position as you fill the arrangement left to right. If a number fails the condition for the current position, you skip it immediately. This prunes entire subtrees from the search space.
At each position i, you only try unused numbers that satisfy num % i == 0 or i % num == 0. Most numbers fail this check for most positions, so the tree shrinks dramatically compared to generating all permutations.
The constraint that n is at most 15 is a strong hint. Even without pruning, 15! is about 1.3 trillion, which is far too large. But with pruning, the number of valid branches is tiny. Position 7, for example, only accepts 1, 7, and 14 from the full range. The higher the position number, the fewer candidates it has, and the tree collapses quickly.
The solution
def countArrangement(n: int) -> int:
count = 0
used = [False] * (n + 1)
def backtrack(pos):
nonlocal count
if pos > n:
count += 1
return
for num in range(1, n + 1):
if not used[num] and (num % pos == 0 or pos % num == 0):
used[num] = True
backtrack(pos + 1)
used[num] = False
backtrack(1)
return count
The structure is the standard choose-explore-unchoose pattern. You fill positions from 1 to n. At each position, you loop through all numbers, skip the ones already used or failing the divisibility check, and recurse. When pos exceeds n, you have filled every position with a valid number, so you increment the count.
The used array tracks which numbers have been placed. Setting used[num] = True before the recursive call is the "choose" step. Setting it back to False after is the "unchoose" step. The divisibility check num % pos == 0 or pos % num == 0 is the pruning condition that makes this problem tractable.
Step-by-step walkthrough
Step 1: Fill position 1. Any number divides by 1, so all are valid.
perm[1] % 1 = 0 is always true, so every unused number is a valid candidate for position 1. Try 1 first.
Step 2: Placed 1 at position 1. Fill position 2. Check divisibility for each unused number.
Unused numbers: {2, 3}. For 2: 2 % 2 = 0, valid. For 3: 3 % 2 != 0 and 2 % 3 != 0, pruned. Only 2 works.
Step 3: Placed 2 at position 2. Fill position 3. Only 3 remains.
For 3: 3 % 3 = 0, valid. Place 3 at position 3. All positions filled. Record [1, 2, 3]. Backtrack.
Step 4: Backtrack to position 1. Try placing 2 at position 1.
2 % 1 = 0, valid. Now fill position 2 with unused numbers {1, 3}.
Step 5: Fill position 2. Check 1 and 3.
For 1: 2 % 1 = 0, valid. For 3: 3 % 2 != 0 and 2 % 3 != 0, pruned. Place 1.
Step 6: Placed 1 at position 2. Fill position 3. Only 3 remains.
For 3: 3 % 3 = 0, valid. Place 3. All positions filled. Record [2, 1, 3]. Backtrack.
Step 7: Backtrack to position 1. Try placing 3 at position 1.
3 % 1 = 0, valid. Now fill position 2 with unused numbers {1, 2}.
Step 8: Fill position 2. Both 1 and 2 are valid.
For 1: 2 % 1 = 0, valid. For 2: 2 % 2 = 0, valid. Try 1 first.
Step 9: Placed 1 at position 2. Fill position 3. Only 2 remains.
For 2: 2 % 3 != 0 and 3 % 2 != 0. Neither condition holds. Pruned. Backtrack to try 2 at position 2.
Step 10: Placed 2 at position 2. Fill position 3. Only 1 remains.
For 1: 3 % 1 = 0, valid. Place 1. All positions filled. Record [3, 2, 1]. Done. Total count = 3.
Notice how many branches get pruned at position 2. Out of the remaining candidates, only numbers where the divisibility condition holds survive. By position 3, most branches have already been eliminated. This is why backtracking works within the given constraints even though n can be up to 15.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Backtracking with pruning | O(k) where k is the number of valid nodes explored | O(n) |
| Bitmask DP | O(n * 2^n) | O(2^n) |
Backtracking time is hard to express precisely. In the worst case it could be O(n!), but the divisibility pruning eliminates most branches. For n = 15, the actual number of recursive calls is far below 15!. The pruning makes it practical.
Backtracking space is O(n) for the recursion stack and the used array.
Bitmask DP is the alternative approach. You represent the set of used numbers as a bitmask and define dp[mask] as the number of beautiful arrangements using exactly the numbers in mask, filling positions 1 through popcount(mask). For each mask, you try adding each unused number that satisfies the divisibility condition for the next position. This runs in O(n * 2^n) time and O(2^n) space. For n = 15, that is about 15 * 32768 = roughly 500,000 operations, which is fast.
The building blocks
Choose-explore-unchoose (backtracking template)
The same skeleton that powers Permutations, N-Queens, and Combination Sum:
def backtrack(state):
if is_complete(state):
record(state)
return
for choice in candidates(state):
if is_valid(choice, state):
make_choice(choice)
backtrack(next_state)
undo_choice(choice)
In Beautiful Arrangement, make_choice is used[num] = True, is_valid is the divisibility check, and undo_choice is used[num] = False. The state is the current position and the set of used numbers.
Bitmask state representation
When n is small (typically 20 or below), you can represent a set of elements as a bitmask. Each bit corresponds to a number. Bit i is 1 if number i is used, 0 otherwise. This lets you store the entire state in a single integer and use bitwise operations to check membership, add elements, and count the population.
def countArrangement(n: int) -> int:
dp = [0] * (1 << n)
dp[0] = 1
for mask in range(1, 1 << n):
pos = bin(mask).count("1")
for num in range(1, n + 1):
if mask & (1 << (num - 1)) and (num % pos == 0 or pos % num == 0):
dp[mask] += dp[mask ^ (1 << (num - 1))]
return dp[(1 << n) - 1]
This DP approach iterates over all 2^n subsets. For each subset, the position being filled is popcount(mask). For each number in the mask, if removing it from the mask gives a valid previous state, you add those arrangements to the current state.
The bitmask DP approach is faster for larger n values because it avoids redundant recomputation. Different orderings of placing the same set of numbers lead to the same subproblem, and the DP table captures this overlap. Backtracking re-explores those overlapping subtrees.
Edge cases
Before submitting, check these:
- n = 1: Only one permutation
[1]. Position 1 has value 1, and 1 % 1 = 0. Answer: 1. - n = 2: Both
[1, 2]and[2, 1]are valid. Answer: 2. - Large positions with few candidates: Position 11 only accepts numbers that divide 11 or that 11 divides. Since 11 is prime, only 1 and 11 work. This severely constrains the tree.
- n = 15 (maximum): The answer is 24679. Both backtracking with pruning and bitmask DP handle this within time limits.
A common mistake is using 0-indexed positions. The problem defines positions as 1-indexed. If you start your loop at 0, the divisibility checks will be wrong (division by zero at position 0, and off-by-one for every other position). Always start at position 1.
From understanding to recall
You see the pattern: fill positions one by one, prune candidates that fail the divisibility check, and count the leaves. It is a direct application of backtracking with constraint checking. But under interview pressure, small details trip people up: forgetting to mark numbers as used, not handling the 1-indexed positions correctly, or missing one of the two divisibility directions.
Spaced repetition fixes recall. You practice writing the backtracking skeleton with the divisibility guard from memory at increasing intervals. After a few rounds, the code flows out automatically when you see a constrained permutation counting problem.
The choose-explore-unchoose pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.
Related posts
- Permutations - The unconstrained version of the same pattern. Beautiful Arrangement adds a divisibility filter to the candidate selection step.
- Permutations II - Permutations with duplicate elements. Shows how the same backtracking template adapts to handle duplicates with sorting and skip logic.
- N-Queens - Another constrained placement problem using backtracking. Instead of divisibility, the constraint is that no two queens attack each other.