526.Beautiful Arrangement

1-

In Leetcode, there are many backTrack problems, some of which are good starting points.

Combination Sum, Factor Combinations, Permutations, Permutations II.

More advanced: Evaluate Division, Word Pattern II, Remove Invalid Parentheses, Basic Calculator

When solving a BT problem, pay attention to whether it’s a Permutation problem, or a Combination.

The problem here is a permutation.

A general recursive template for backtracking may look like this:

 helper (parameters of given data and current recursive level) {
        // Handle base cases, i.e. the last level of recursive call
        if (level == lastLevel) {
            record result;
            return sth;
        }
        // Otherwise permute every possible value for this level.
        for (every possible value for this level) {
            helper(parameters of given data and next recursive level);
        }
        return sth;
    }

class Solution {
    int cnt = 0;
    public int countArrangement(int N) {
        cnt = 0;
        if(N == 0)
            return 0;
        helper(N, 1, new int[N+1]);
        return cnt;
    }
    public void helper(int N, int pos, int[] used){
        if(pos > N){
            cnt++;
            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;
            }
        }
    }
}