Course4all
Join us on telegram
Home/dsa/Backtracking/Beautiful Arrangement

Beautiful Arrangement

Master this topic with zero to advance depth.

Beautiful Arrangement

The divisibility Rule

An arrangement is beautiful if for every position ii (1-indexed):

  1. perm[i] % i == 0 OR
  2. i % perm[i] == 0

Pruning in Backtracking

Instead of generating all N!N! permutations and checking them, we check the condition at each step. If a number cannot be placed at the current index, we prune the entire branch.

Count the number of beautiful arrangements of numbers 1 to N. Includes visual placement trace.

Medium

Examples

Input: n = 2
Output: 2
Approach 1

Level I: Backtracking with Pruning

Intuition

Try placing each available number in the current position, checking the rule.

Use a visited array to track used numbers. At each position idx, iterate from 1 to N. If i is not used and satisfies the beautiful rule, place it and recurse.

⏱ O(K) where K is the number of valid permutations.💾 O(N)

Detailed Dry Run

N=3 1. Pos 1: Try 1 (1%1==0). OK. 2. Pos 2: Try 2 (2%2==0). OK. 3. Pos 3: Try 3 (3%3==0). OK. (Result=1) 4. Pos 2: Try 3 (3%2!=0, 2%3!=0). Fail.
java
class Solution {
    int count = 0;
    public int countArrangement(int n) {
        boolean[] visited = new boolean[n + 1];
        backtrack(n, 1, visited);
        return count;
    }
    private void backtrack(int n, int pos, boolean[] visited) {
        if (pos > n) {
            count++; return;
        }
        for (int i = 1; i <= n; i++) {
            if (!visited[i] && (i % pos == 0 || pos % i == 0)) {
                visited[i] = true;
                backtrack(n, pos + 1, visited);
                visited[i] = false;
            }
        }
    }
}
← Previous QuestionRemove Invalid Parentheses
Next Question →Unique Paths III