Suppose you haveNintegers from 1 to N. We define a beautiful arrangement as an array that is constructed by theseNnumbers successfully if one of the following is true for the ithposition (1 <= i <= N) in this array:

1. The number at the i-th position is divisible by i.
2. i is divisible by the number at the i-th position.

Now given N, how many beautiful arrangements can you construct?

class Solution {
    public int countArrangement(int N) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> line = new ArrayList<>();
        boolean[] visited = new boolean[N];

        helper(res, line, visited, N);

        return res.size();
    }

    public void helper(List<List<Integer>> res, List<Integer> line, boolean[] visited, int n) {
        if(line.size() == n) {
            res.add(new ArrayList<>(line));
            return;
        }

        for(int i = 1; i <= n; i++) {
            if(visited[i - 1])
                continue;

            int next = line.size() + 1;
            if(i % next == 0 || next % i == 0) {
                line.add(i);
                visited[i - 1] = true;
                helper(res, line, visited, n);
                visited[i - 1] = false;
                line.remove(line.size() - 1);
            }
        }
    }
}

leetcode答案里有个更好的方法，省略了一些不必要的操作，例如把每种结果都记录下来本来不需要

class Solution {
    public int countArrangement(int N) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> line = new ArrayList<>();
        boolean[] visited = new boolean[N];

        helper(res, line, visited, N);

        return res.size();
    }

    public void helper(List<List<Integer>> res, List<Integer> line, boolean[] visited, int n) {
        if(line.size() == n) {
            res.add(new ArrayList<>(line));
            return;
        }

        for(int i = 1; i <= n; i++) {
            if(visited[i - 1])
                continue;

            int next = line.size() + 1;
            if(i % next == 0 || next % i == 0) {
                line.add(i);
                visited[i - 1] = true;
                helper(res, line, visited, n);
                visited[i - 1] = false;
                line.remove(line.size() - 1);
            }
        }
    }
}