Beautiful Arrangement
Medium · Backtracking · Explanation and code example
Memoized Backtracking by Used Positions
How it works
Assign numbers one through n to still-empty positions that divide the number or are divisible by it. The filled-position state determines the next number and all future choices, so memoize the number of completions for that state. Backtrack each temporary position assignment.
Steps
- Try each empty position satisfying either divisibility condition.
- Mark it filled, recurse with the next number, then undo it.
- Memoize completed states and return one after all numbers are placed.
Complexity
- Time: O(n² × 2^n) conservative bound including copied/hashed string states.
- Space: O(n × 2^n) for string-key memo storage.
Things to watch for
- Either direction of divisibility qualifies.
- Undo a position after returning.
- The Python example copies a state string; account for that work rather than claiming a bitmask bound.
Python code example
from functools import lru_cache
class Solution:
def countArrangement(self, n: int) -> int:
@lru_cache(None)
def dfs(number, filled):
if number == n + 1:
return 1
count = 0
for position in range(1, n + 1):
if filled[position] == "x" and (number % position == 0 or position % number == 0):
next_state = filled[:position] + "o" + filled[position + 1:]
count += dfs(number + 1, next_state)
return count
return dfs(1, "x" * (n + 1))
C++ code example
class Solution {
public:
int countArrangement(int n) {
return dfs(n, 1, string(n + 1, 'x'), {});
}
private:
int dfs(int n, int num, string&& filled, unordered_map<string, int>&& mem) {
if (num == n + 1)
return 1;
if (const auto it = mem.find(filled); it != mem.cend())
return it->second;
int count = 0;
for (int i = 1; i <= n; ++i)
if (filled[i] == 'x' && (num % i == 0 || i % num == 0)) {
filled[i] = 'o';
count += dfs(n, num + 1, std::move(filled), std::move(mem));
filled[i] = 'x';
}
return mem[filled] = count;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.