Backtracking — Beautiful Arrangement

↗ LeetCode: Beautiful Arrangement · Medium · pattern chapter →

Asked atMetaAmazonGoogle

Count permutations of 1..n where for every position i (1-indexed), a[i] % i == 0 OR i % a[i] == 0.

Example 1 — n=2 → 2Example 2 — n=1 → 1

Constraints — 1 ≤ n ≤ 15. Brute enumerates n! permutations — 15! ≈ 10¹² ops = 20 min at 10⁹ ops/sec. Backtracking with divisibility pruning + bitmask visited is O(n·2ⁿ) ≈ 5·10⁵ ops at n=15.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Backtracking with used-mask

java

int countArrangement(int n) {
    return dfs(n, 1, new boolean[n + 1]);
}
int dfs(int n, int pos, boolean[] used) {
    if (pos > n) return 1;
    int c = 0;
    for (int v = 1; v <= n; v++)
        if (!used[v] && (v % pos == 0 || pos % v == 0)) {
            used[v] = true;
            c += dfs(n, pos + 1, used);
            used[v] = false;
        }
    return c;
}

Approach 2 — Bitmask DP (n ≤ 15)

dp[mask] = # ways to fill first popcount(mask) positions using selected numbers.

java

int countArrangementBM(int n) {
    int full = 1 << n;
    int[] dp = new int[full];
    dp[0] = 1;
    for (int mask = 1; mask < full; mask++) {
        int pos = Integer.bitCount(mask);
        for (int v = 1; v <= n; v++) {
            int bit = 1 << (v - 1);
            if ((mask & bit) == 0) continue;
            if (v % pos == 0 || pos % v == 0) dp[mask] += dp[mask ^ bit];
        }
    }
    return dp[full - 1];
}

Complexity — Both O(n · 2ⁿ); DP cleaner for n ≤ 15.

Try it yourself

Complexity summary

Approach	Time	Space	Grade
Backtracking	O(n · 2ⁿ)	O(n)	canonical
Bitmask DP	O(n · 2ⁿ)	O(2ⁿ)	iterative

When to use which

Small n → either.
n ≤ 15 → bitmask DP is clean.
Larger n → no polynomial algo.

✨AI Study CompanionBeta

Was this page helpful?

📚 Related problems

Backtracking — Beautiful Arrangement ​

Approach 1 — Backtracking with used-mask ​

Approach 2 — Bitmask DP (n ≤ 15) ​

Try it yourself ​

Complexity summary ​

When to use which ​

Related problems ​