Log inSign up
mediumLeetCodeNot Started

Beautiful Arrangement

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on LeetCode
Lesson

Problem Statement

Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n), either of the following is true:

1. perm[i] is divisible by i (perm[i] % i == 0). 2. i is divisible by perm[i] (i % perm[i] == 0).

Given an integer n, return the number of beautiful arrangements that you can construct.

Example 1:

Input: n = 2
Output: 2
Explanation: The first beautiful arrangement is [1,2]: perm[1]=1 (1%1==0), perm[2]=2 (2%2==0). The second is [2,1]: perm[1]=2 (2%1==0), perm[2]=1 (2%1==0).

Example 2:

Input: n = 1
Output: 1
Explanation: The only permutation is [1], which is beautiful.

Constraints:

  • 1 <= n <= 15

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master variable ordering heuristics in constraint satisfaction problems (search most constrained variables first).
  • Implement in-place permutation backtracking with divisibility pruning.
  • Formulate bitmask state compression for permutation counting (dp[mask]).

1. Generate All Permutations and Validate

Intuition

Build the entire array of length N. Once a full permutation is assembled, loop through indices 1 to N to verify the divisibility property.

Algorithm

  1. Step 1: Generate all N! permutations of numbers from 1 to N using standard backtracking.
  2. Step 2: For each completed permutation, iterate through indices i = 1 to N.
  3. Step 3: Check if perm[i-1] is divisible by i or i is divisible by perm[i-1].
  4. Step 4: If all N positions satisfy the condition, increment the valid arrangement count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 bool isBeautiful(const std::vector<int>& perm, int n) {
7 for (int i = 1; i <= n; i++) {
8 if (perm[i - 1] % i != 0 && i % perm[i - 1] != 0) return false;
9 }
10 return true;
11 }
12
13 void permute(int index, int n, std::vector<int>& perm, std::vector<bool>& used, int& count) {
14 if (index == n) {
15 if (isBeautiful(perm, n)) count++;
16 return;
17 }
18 for (int i = 1; i <= n; i++) {
19 if (!used[i]) {
20 used[i] = true;
21 perm.push_back(i);
22 permute(index + 1, n, perm, used, count);
23 perm.pop_back();
24 used[i] = false;
25 }
26 }
27 }
28
29 int countArrangement(int n) {
30 int count = 0;
31 std::vector<int> perm;
32 std::vector<bool> used(n + 1, false);
33 permute(0, n, perm, used, count);
34 return count;
35 }
36};
37
38int main() {
39 Solution solver;
40 std::cout << "Beautiful Arrangements for N = 2: " << solver.countArrangement(2) << "\n";
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(N! * N) — Generates all N! permutations and verifies each in O(N) time.
  • Space complexity: O(N) — O(N) recursion stack and visited array.

2. Forward Backtracking with Divisibility Pruning (1 to N)

Intuition

Function backtrack(pos) attempts to place an unused number num in position pos. If divisible, mark num used, recurse on pos + 1, and unmark. Prunes dead branches immediately before assembling complete permutations.

Algorithm

  1. Step 1: Define backtrack(pos) starting from pos = 1 up to N.
  2. Step 2: For each unused number num from 1 to N, check if (num % pos == 0 || pos % num == 0).
  3. Step 3: If divisible, mark num as used and recurse on pos + 1.
  4. Step 4: Backtrack by unmarking num after returning.
  5. Step 5: When pos > N, increment valid arrangement count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 void backtrack(int pos, int n, std::vector<bool>& used, int& count) {
7 if (pos > n) {
8 count++;
9 return;
10 }
11 for (int num = 1; num <= n; num++) {
12 if (!used[num] && (num % pos == 0 || pos % num == 0)) {
13 used[num] = true;
14 backtrack(pos + 1, n, used, count);
15 used[num] = false;
16 }
17 }
18 }
19
20 int countArrangement(int n) {
21 int count = 0;
22 std::vector<bool> used(n + 1, false);
23 backtrack(1, n, used, count);
24 return count;
25 }
26};
27
28int main() {
29 Solution solver;
30 std::cout << "Forward Backtracking for N = 4: " << solver.countArrangement(4) << "\n";
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(Valid States) — Explores strictly valid prefix configurations.
  • Space complexity: O(N) — O(N) recursion stack and boolean visited array.

3. Reverse Backtracking (N down to 1) & Bitmask Pruning (Gold Standard)

Intuition

At pos = n, a number num can only be placed if num == n or num is a divisor of n (since num < n). This eliminates most choices at the root level, making the search tree up to 10x smaller than forward search.

Algorithm

  1. Step 1: Start backtracking from pos = N down to 1 (most constrained variable heuristic).
  2. Step 2: For each unused number num from 1 to N, verify if (num % pos == 0 || pos % num == 0).
  3. Step 3: Since large positions have very few valid divisors, prune dead subtrees at the root.
  4. Step 4: Mark num used, recurse on pos - 1, and backtrack by unmarking num.
  5. Step 5: When pos == 0, a complete beautiful arrangement is formed; increment count.

Reverse Backtracking Decision Tree Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Initialize reverse search at position pos = 2 with used = [F, F, F]
Visual state
Values and pointers at this exact step
tree
Root
pos: 2, used: []

Node order shown; add connections to display explicit tree edges.

Variables at this step
pos
2
used
[false,false,false]
validCount
0
Check / comparison
pos = 2, candidate numbers = [1, 2]
Decision / next transition
Evaluate divisibility for num = 1 and num = 2 at pos 2
Why this step matters

Initialize reverse search at position pos = 2 with used = [F, F, F].

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 void backtrack(int pos, int n, std::vector<bool>& used, int& count) {
7 if (pos == 0) {
8 count++;
9 return;
10 }
11 for (int num = 1; num <= n; num++) {
12 if (!used[num] && (num % pos == 0 || pos % num == 0)) {
13 used[num] = true;
14 backtrack(pos - 1, n, used, count);
15 used[num] = false;
16 }
17 }
18 }
19
20 int countArrangement(int n) {
21 int count = 0;
22 std::vector<bool> used(n + 1, false);
23 backtrack(n, n, used, count);
24 return count;
25 }
26};
27
28int main() {
29 Solution solver;
30 std::cout << "Optimal Reverse Backtracking for N = 10: " << solver.countArrangement(10) << "\n";
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(Valid States) (Fastest practical execution) — Minimizes branching factor at root nodes.
  • Space complexity: O(N) — O(N) recursion depth and visited flags.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force All PermutationsO(N! * N)O(N)Generate all N! permutations and validate each one element by element.No early branch pruning
2.Backtracking (1 to N) (Better)O(Valid States) << O(N!)O(N)Only place numbers that satisfy divisibility at current position pos from 1 to N.Position ordering
3.Reverse Backtracking (N down to 1) / Bitmask DP (Optimal)OptimalO(Valid States) (Fastest)O(N)Fill positions from N down to 1. Larger numbers have strict divisor constraints, eliminating dead subtrees earliest.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using 0-indexed values for modulo instead of 1-indexed (e.g. (i + 1) vs i).

Pitfall 2:

Checking only num % pos == 0 and forgetting pos % num == 0.

Crucial Edge Cases to Validate:

  • n = 1 -> returns 1.
  • n = 15 (maximum constraint) -> completes in < 50ms using reverse backtracking.
  • Prime positions (e.g. pos = 13, 11) -> only accept 1 or themselves when num <= n.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the 'Most Constrained Variable' heuristic: filling pos = N down to 1 prunes the tree at the shallowest depth.
  2. Discuss Bitmask Memoization memo[mask] as an alternate O(n * 2n) dynamic programming solution.
  3. State time complexity clearly: while worst-case theoretical upper bound is O(N!), the actual valid search states are dramatically smaller due to divisibility pruning.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is reverse backtracking (from pos = n down to 1) faster than forward backtracking (from pos = 1 to n)?

Back to DSA Sheet