0526. Beautiful Arrangement

https://leetcode.com/problems/beautiful-arrangement

Description

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 <= n <= 15

ac

class Solution {
    int res = 0;
    boolean[] visiting;

    public int countArrangement(int N) {
        // edge cases

        visiting = new boolean[N+1];
        backtrack(1, N);

        return res;
    }

    private void backtrack(int kth, int n) {
        // exit
        if (kth == n + 1) {
            res++;
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (visiting[i]) continue;
            if (i % kth == 0 || kth % i == 0) {
                visiting[i] = true;
                backtrack(kth+1, n);
                visiting[i] = false;
            }
        }
    }
}

same code, slight change. starting from backward accelerate the process because it avoids entering wrong path in earlier stage.

class Solution {
    int res = 0;
    boolean[] visiting;

    public int countArrangement(int N) {
        // edge cases

        visiting = new boolean[N+1];
        backtrack(N, N);

        return res;
    }

    private void backtrack(int kth, int n) {
        // exit
        if (kth == 0) {
            res++;
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (visiting[i]) continue;
            if (i % kth == 0 || kth % i == 0) {
                visiting[i] = true;
                backtrack(kth-1, n);
                visiting[i] = false;
            }
        }
    }
}