Beautiful Arrangement

给一个数字n, 返回所有可能的组合数组的个数, 这个数组满足两个条件, 一个是i上的数能乘除array[i], 一个是array[i]能整除i. 这个题直接dfs其实很好写, 但是太慢了, 加上剪枝也过不去. 看了下答案, 答案也是dfs和剪枝. 但是他用一个memo数组,表示use[i]表示是否用i这个index上的digit, 所以答案的dfs是直接数数组的个数, 即每个递归都表示是否在当前pos上的digit可以表示一个beautiful排序. 如果pos > N, 那么就意味着找到了一个数组满足这个条件.

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