Beautiful Arrangement Problem

Description

LeetCode Problem 526.

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:

• perm[i] is divisible by i.
• i is divisible by perm[i].

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

Example 1:

 1 2 3 4 5 6 7 8 9 Input: n = 2 Output: 2 Explanation: The first beautiful arrangement is [1,2]: - perm[1] = 1 is divisible by i = 1 - perm[2] = 2 is divisible by i = 2 The second beautiful arrangement is [2,1]: - perm[1] = 2 is divisible by i = 1 - i = 2 is divisible by perm[2] = 1

Example 2:

 1 2 Input: n = 1 Output: 1

Constraints:

• 1 <= n <= 15

Sample C++ Code using Backtracking

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public: bool seen[16] = {}; int res = 0; int dfs(int n, int pos = 1) { if (pos > n) return res++; for (int i = 1; i <= n; i++) { if (!seen[i] && (i % pos == 0 || pos % i == 0)) { seen[i] = true; dfs(n, pos + 1); seen[i] = false; } } return res; } int countArrangement(int n) { if (n < 4) return n; return dfs(n); } };