Beautiful Arrangement: Constraint-Filtered Permutation Backtracking

Problem Statement#

You are given a positive integer n. Count the number of beautiful arrangements of the numbers 1 through n. An arrangement perm (1-indexed) is beautiful if, for every position i, at least one of the following holds:

• perm[i] is divisible by i, OR
• i is divisible by perm[i].

For n = 2, the answer is 2: arrangements [1, 2] and [2, 1] are both beautiful. For n = 15, the answer is 24679. The constraint n <= 15 hints that an exponential solution is expected, but with hard pruning.

Why This Problem Matters#

LeetCode 526 is a sneaky-hard medium that Amazon, Google, and Microsoft use to test two skills: writing a clean permutation backtracking template and recognizing when to add bitmask DP for memoization. With n <= 15, candidates often default to "generate all n! permutations and filter," which TLEs on n = 15 (15! is over a trillion). Pruning at the position level cuts the work to roughly the count of valid arrangements, which is dramatically smaller.

The bitmask DP variant introduces a generalizable technique for permutation counting that shows up across competitive programming and dynamic systems.

The Core Insight (decision tree / state space)#

State: position pos (1 through n) and a used[] array (or bitmask) tracking which numbers have been placed. Decision: which unused number num to put at position pos?

The pruning gold: only consider num values where num % pos == 0 OR pos % num == 0. This often narrows the candidates from n - placed to a tiny handful. Precomputing valid candidates per position avoids redundant divisibility checks.

For bitmask DP, the state becomes the bitmask of used numbers. The position is implicit — popcount(mask) + 1. Transition: for each unused number num valid at position popcount(mask) + 1, add dp[mask] to dp[mask | (1 << (num - 1))]. Final answer is dp[(1 << n) - 1].

Visual Dry Run (recursion tree)#

For n = 4:

position 1: any number (everything divides 1) -> 4 choices
  pick 1 -> position 2: candidates that share divisibility with 2: {2, 4}
    pick 2 -> position 3: candidates with 3: {3} (only 3 divides 3 or is divisible)
      pick 3 -> position 4: candidates with 4: {4}
        pick 4 -> ARRANGEMENT [1,2,3,4] valid
    pick 4 -> position 3: {3}
      pick 3 -> position 4: only unused {2}; 4 % 2 == 0, valid -> [1,4,3,2]
  pick 2 -> position 2: ...
  pick 3 -> position 2: ...
  pick 4 -> position 2: ...

Notice how at position 3, only 3 qualifies; the tree narrows fast because most positions have very few divisibility-compatible candidates.

Solution (Optimal) — Python + JavaScript with backtracking template, complexity#

Backtracking with precomputed candidates:

def countArrangement(n):
    valid = [[] for _ in range(n + 1)]
    for pos in range(1, n + 1):
        for num in range(1, n + 1):
            if num % pos == 0 or pos % num == 0:
                valid[pos].append(num)
 
    used = [False] * (n + 1)
    count = 0
 
    def backtrack(pos):
        nonlocal count
        if pos > n:
            count += 1
            return
        for num in valid[pos]:
            if not used[num]:
                used[num] = True
                backtrack(pos + 1)
                used[num] = False
 
    backtrack(1)
    return count

function countArrangement(n) {
  const valid = Array.from({ length: n + 1 }, () => []);
  for (let pos = 1; pos <= n; pos++) {
    for (let num = 1; num <= n; num++) {
      if (num % pos === 0 || pos % num === 0) valid[pos].push(num);
    }
  }
  const used = new Array(n + 1).fill(false);
  let count = 0;
  const backtrack = (pos) => {
    if (pos > n) {
      count++;
      return;
    }
    for (const num of valid[pos]) {
      if (!used[num]) {
        used[num] = true;
        backtrack(pos + 1);
        used[num] = false;
      }
    }
  };
  backtrack(1);
  return count;
}

Bitmask DP alternative — O(n times 2^n) time, O(2^n) space:

def countArrangementDP(n):
    dp = [0] * (1 << n)
    dp[0] = 1
    for mask in range(1 << n):
        pos = bin(mask).count('1') + 1
        if pos > n:
            continue
        for num in range(1, n + 1):
            if (mask >> (num - 1)) & 1:
                continue
            if num % pos == 0 or pos % num == 0:
                dp[mask | (1 << (num - 1))] += dp[mask]
    return dp[(1 << n) - 1]

Complexity: backtracking runs in O(k) where k is the number of valid arrangements (much less than n!). Bitmask DP is O(n times 2^n). For n = 15, both finish in milliseconds; backtracking is typically faster because pruning kicks in.

Common Mistakes#

• Generating all permutations and filtering — guaranteed TLE for n = 15.
• Forgetting that position 1 accepts every number (everything divides 1). Skipping this leads to off-by-one errors.
• In bitmask DP, computing the position from the bitmask incorrectly. Always use popcount(mask) + 1.
• Not precomputing valid[pos]. The divisibility check inside the recursion is a constant factor that adds up.

Interview Tips#

• Mention both approaches: "Backtracking with pruning is fastest in practice; bitmask DP gives a clean O(n times 2^n) bound."
• Walk through n = 4 on the board — small enough to trace, big enough to show the pruning.
• Note that position 1 trivially accepts everything; this is a common corner case.
• Discuss when bitmask DP wins (when you need to memoize across many similar states, e.g., counting variations).

Follow-up Questions#

• LeetCode 996 (Number of Squareful Arrays): adjacent-pair constraint instead of position-value.
• LeetCode 47 (Permutations II): permutations with duplicate values.
• General permutation counting under arbitrary pairwise constraints — bitmask DP shines.
• What if you need ONE valid arrangement instead of the count? Backtracking returns immediately on first success.

Key Takeaways#

• Beautiful Arrangement is a permutation backtracking problem with strong divisibility pruning.
• Precompute valid[pos] so the inner loop skips invalid candidates instantly.
• Bitmask DP gives a clean O(n times 2^n) bound for n <= 15.
• The naive "generate then filter" approach TLEs; pruning is mandatory.
• Position 1 is a sentinel: it accepts every number (every integer divides 1).
• A FAANG-favorite for testing both backtracking discipline and bitmask DP fluency.

Sources:

• Beautiful Arrangement - LeetCode
• 526. Beautiful Arrangement - In-Depth Explanation