Problem Description

The "Beautiful Arrangement" problem asks you to determine how many permutations of the numbers from 1 to n are "beautiful." A permutation is considered beautiful if, for every position i (1-indexed) in the array, either:

• perm[i] is divisible by i, or
• i is divisible by perm[i]

The input is a single integer n (where 1 <= n <= 15), and you must return the total number of beautiful arrangements possible. Each number from 1 to n must be used exactly once in each arrangement; no number is reused.

Thought Process

At first glance, this problem seems to require checking all possible permutations of the numbers from 1 to n, and counting those that meet the divisibility conditions at every position. For small n, this brute-force approach is possible, but as n increases, the number of permutations (n!) grows rapidly.

To solve this efficiently, we need to avoid generating every permutation explicitly. Instead, we can use backtracking, where we build the arrangement one position at a time, only placing numbers that satisfy the divisibility condition at each step. This prunes many invalid possibilities early, making the solution much faster.

As we explore each possible arrangement recursively, we mark numbers as used so that no number is repeated. This approach is more efficient than brute-force permutation generation and checking.

Solution Approach

The most effective way to solve this problem is to use backtracking with pruning. Here are the main steps:

1. Recursive Backtracking:
   • We define a recursive function that tries to place a number at each position from 1 to n.
   • At each position i, we iterate through all numbers not yet used.
   • For each unused number, we check if it is divisible by i or i is divisible by the number.
   • If the condition is satisfied, we mark the number as used and recurse to the next position.
   • After recursion, we unmark the number (backtrack) to explore other possibilities.
2. Base Case:
   • If we reach position n+1, it means a valid arrangement has been found. We increment our count.
3. Optimization:
   • We use a boolean array (or bitmask) to keep track of which numbers have been used.
   • By only considering valid numbers at each step, we avoid a huge number of unnecessary recursive calls.

This approach is much faster than checking all n! permutations, especially as n grows.

Example Walkthrough

Let's walk through the algorithm with n = 3:

• We want to count the number of permutations of [1, 2, 3] that are beautiful.
• Step 1: Position 1 (i=1)
  • Try placing 1: 1 % 1 == 0 (valid)
  • Try placing 2: 2 % 1 == 0 (valid)
  • Try placing 3: 3 % 1 == 0 (valid)
• Step 2: For each valid choice at position 1, try to fill position 2 with remaining numbers:
  • If position 1 = 1, remaining = [2, 3]
  • At position 2, try 2: 2 % 2 == 0 (valid), try 3: 3 % 2 != 0 and 2 % 3 != 0 (invalid)
  • Continue recursively for each branch, only proceeding if the divisibility condition holds.
• Continue: Repeat for positions 3, updating used numbers and checking conditions.
• Result: For n=3, there are 3 beautiful arrangements: [1,2,3], [3,2,1], [2,1,3]

The backtracking approach only explores valid branches, pruning invalid ones early, which is much more efficient than generating all 6 permutations and checking each.

Time and Space Complexity

Brute-Force Approach:

• Time Complexity: O(n!) — since all permutations are generated and checked.
• Space Complexity: O(n) — for recursion stack or array to store current permutation.

• Time Complexity: O(n!) in the worst case, but usually much less due to pruning. For each position, only a subset of numbers are valid, so the actual number of recursive calls is much lower.
• Space Complexity: O(n) — for the recursion stack and the used array/bitmask.

The optimized approach is feasible for n <= 15 as required by the problem constraints.

Summary

The "Beautiful Arrangement" problem is a classic example of using backtracking with pruning to efficiently search for valid permutations under specific constraints. By checking divisibility conditions as we build each arrangement, we avoid unnecessary computation and solve the problem much faster than brute-force. The key insight is to only consider valid candidates at each step and backtrack as soon as a condition is violated, making the algorithm both elegant and efficient.

Code Implementation

class Solution:
    def countArrangement(self, n: int) -> int:
        def backtrack(pos, used):
            if pos > n:
                return 1
            count = 0
            for num in range(1, n+1):
                if not used[num] and (num % pos == 0 or pos % num == 0):
                    used[num] = True
                    count += backtrack(pos+1, used)
                    used[num] = False
            return count

        used = [False] * (n+1)
        return backtrack(1, used)
      

class Solution {
public:
    int countArrangement(int n) {
        vector<bool> used(n + 1, false);
        return backtrack(1, n, used);
    }
private:
    int backtrack(int pos, int n, vector<bool>& used) {
        if (pos > n) return 1;
        int count = 0;
        for (int num = 1; num <= n; ++num) {
            if (!used[num] && (num % pos == 0 || pos % num == 0)) {
                used[num] = true;
                count += backtrack(pos + 1, n, used);
                used[num] = false;
            }
        }
        return count;
    }
};
      

class Solution {
    public int countArrangement(int n) {
        boolean[] used = new boolean[n + 1];
        return backtrack(1, n, used);
    }

    private int backtrack(int pos, int n, boolean[] used) {
        if (pos > n) return 1;
        int count = 0;
        for (int num = 1; num <= n; num++) {
            if (!used[num] && (num % pos == 0 || pos % num == 0)) {
                used[num] = true;
                count += backtrack(pos + 1, n, used);
                used[num] = false;
            }
        }
        return count;
    }
}
      

var countArrangement = function(n) {
    function backtrack(pos, used) {
        if (pos > n) return 1;
        let count = 0;
        for (let num = 1; num <= n; num++) {
            if (!used[num] && (num % pos === 0 || pos % num === 0)) {
                used[num] = true;
                count += backtrack(pos + 1, used);
                used[num] = false;
            }
        }
        return count;
    }
    let used = new Array(n + 1).fill(false);
    return backtrack(1, used);
};