Beautiful Arrangement

medium array dp backtracking bitmask

Problem

Count permutations perm[1..n] such that for every i, perm[i] is divisible by i or i is divisible by perm[i].

Inputn = 4

Output8

Backtracking from position 1; or bitmask DP over chosen subset.

def count_arrangement(n):
    used = [False] * (n + 1)
    def back(pos):
        if pos > n: return 1
        s = 0
        for x in range(1, n + 1):
            if used[x] or (x % pos != 0 and pos % x != 0): continue
            used[x] = True
            s += back(pos + 1)
            used[x] = False
        return s
    return back(1)

function countArrangement(n) {
  const used = new Array(n + 1).fill(false);
  function back(pos) {
    if (pos > n) return 1;
    let s = 0;
    for (let x = 1; x <= n; x++) {
      if (used[x] || (x % pos !== 0 && pos % x !== 0)) continue;
      used[x] = true;
      s += back(pos + 1);
      used[x] = false;
    }
    return s;
  }
  return back(1);
}

class Solution {
    boolean[] used;
    int N;
    public int countArrangement(int n) {
        used = new boolean[n + 1]; N = n;
        return back(1);
    }
    int back(int pos) {
        if (pos > N) return 1;
        int s = 0;
        for (int x = 1; x <= N; x++) {
            if (used[x] || (x % pos != 0 && pos % x != 0)) continue;
            used[x] = true;
            s += back(pos + 1);
            used[x] = false;
        }
        return s;
    }
}

vector used;
int N;
int back(int pos) {
    if (pos > N) return 1;
    int s = 0;
    for (int x = 1; x <= N; x++) {
        if (used[x] || (x % pos != 0 && pos % x != 0)) continue;
        used[x] = true;
        s += back(pos + 1);
        used[x] = false;
    }
    return s;
}
int countArrangement(int n) { N = n; used.assign(n + 1, false); return back(1); }

Explanation

We build the permutation one slot at a time using backtracking, and count every full arrangement that satisfies the divisibility rule.

The function back(pos) tries to fill position pos. It loops over every number x from 1 to n and skips it if it is already used or if it fails the rule. The rule is x % pos == 0 or pos % x == 0 — the value must divide the position or the position must divide the value.

When a number fits, we mark it used, recurse into back(pos + 1), then undo the mark before trying the next candidate. That undo step is the heart of backtracking — it frees the number for other branches.

The base case is pos > n: every slot is filled successfully, so that path counts as 1. Summing the recursion totals all valid arrangements.

Example: n = 4. Placing numbers slot by slot under the divisibility rule yields exactly 8 beautiful arrangements.

Time: O(n!) Space: O(n)