package LeetCode_526

/**
 * 526. Beautiful Arrangement
 * https://leetcode.com/problems/beautiful-arrangement/
 * 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:
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. 1 <= n <= 15
 * */
class Solution {
    /*
    * Solution: DFS, to check the numbers of 1-n if can match beautiful arrangement,
    * Time:O(2^n), Space:O(2^n)
    * */
    private var result = 0

    fun countArrangement(n: Int): Int {
        val used = BooleanArray(n+1)
        dfs(n,n,used)
        return result
    }

    private fun dfs(N: Int, n: Int, used: BooleanArray) {
        if (n == 0) {
            result++
            return
        }
        for (i in 1..N) {
            if (used[i] || i % n != 0 && n % i != 0) {
                continue
            }
            used[i] = true
            dfs(N, n - 1, used)
            used[i] = false
        }
    }
}