Graceful arrangement

You can add numbers to the list of targets from left to right.

Specifically, we define the function backtrack(index,n), which attempts to put a number into the position index. Where n is the length of the permutation. In the current function, we first find an unused number that meets the condition, and then backtrack(index+1,n) recursively. When the function is finished, we try the next unused number that meets the condition back to the current level.

During backtracking, we can use the VIS array to mark which numbers have been used. Every time we select a number x, we mark vis[x] as true, and when the backtracking is complete, we set it to false.

In particular, in order to optimize the backtracking efficiency, we can preprocess the numbers that meet the conditions at each position and save them with the two-dimensional array match. When we try to put a number into the position index, we simply iterate over match[index].

class Solution {
    List<Integer>[] match;
    boolean[] vis;
    int num;

    public int countArrangement(int n) {
        vis = new boolean[n + 1];
        match = new List[n + 1];
        for (int i = 0; i <= n; i++) {
            match[i] = new ArrayList<Integer>();
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i % j == 0 || j % i == 0) {
                    match[i].add(j);
                }
            }
        }
        backtrack(1, n);
        return num;
    }

    public void backtrack(int index, int n) {
        if (index == n + 1) {
            num++;
            return;
        }
        for (int x : match[index]) {
            if(! vis[x]) { vis[x] =true;
                backtrack(index + 1, n);
                vis[x] = false; }}}}Copy the code