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;
}
}
}
}