526. Beautiful Arrangement

Problem Description

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

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

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 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:

Input: n = 1
Output: 1

Constraints:

• 1 <= n <= 15

Python Solution

class Solution:
    def countArrangement(self, n: int) -> int:
        def backtrack(pos: int, used: set) -> int:
            if pos > n:
                return 1
            
            count = 0
            for i in range(1, n + 1):
                if i not in used and (i % pos == 0 or pos % i == 0):
                    used.add(i)
                    count += backtrack(pos + 1, used)
                    used.remove(i)
            return count
        
        return backtrack(1, set())

Java Solution

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

C++ Solution

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

JavaScript Solution

/**
 * @param {number} n
 * @return {number}
 */
var countArrangement = function(n) {
    const used = new Set();
    
    function backtrack(pos) {
        if (pos > n) {
            return 1;
        }
        
        let count = 0;
        for (let i = 1; i <= n; i++) {
            if (!used.has(i) && (i % pos === 0 || pos % i === 0)) {
                used.add(i);
                count += backtrack(pos + 1);
                used.delete(i);
            }
        }
        return count;
    }
    
    return backtrack(1);
};

C# Solution

public class Solution {
    private int count = 0;
    
    public int CountArrangement(int n) {
        bool[] used = new bool[n + 1];
        Backtrack(n, 1, used);
        return count;
    }
    
    private void Backtrack(int n, int pos, bool[] used) {
        if (pos > n) {
            count++;
            return;
        }
        
        for (int i = 1; i <= n; i++) {
            if (!used[i] && (i % pos == 0 || pos % i == 0)) {
                used[i] = true;
                Backtrack(n, pos + 1, used);
                used[i] = false;
            }
        }
    }
}