Backtracking - Beautiful Arrangement

Given an integer n, count the number of beautiful arrangements you can construct using integers 1 to n. A beautiful arrangement is one where for every i, either perm[i] is divisible by i or i is divisible by perm[i].

Input: n = 2 → Output: 2

Input: n = 1 → Output: 1

Use backtracking: at each position pos (1-indexed), try placing each unused number. A number k is valid at position pos if k % pos == 0 or pos % k == 0. Use a visited array to track used numbers.

Maintain a boolean visited[] of size n+1.
At each position pos from 1 to n, try all numbers 1..n that are not visited.
Check divisibility condition; if valid, mark visited and recurse to pos+1.
When pos > n, increment count. Backtrack by unmarking visited.

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 k = 1; k <= n; k++) { if (!visited[k] && (k % pos == 0 || pos % k == 0)) { visited[k] = true; backtrack(n, pos + 1, visited); visited[k] = false; } } } }

Time Complexity: O(k) where k is number of valid arrangements
Space Complexity: O(N) — visited array + stack