0 backtracking / dynamic programming medium leetcode526. Beautiful arrangement

526. A beautiful arrangement
Suppose there is a follow-up 1 To n Of n It's an integer . Use these integers to construct an array perm（ Subscript from 1 Start ）, As long as the following conditions are met One of , The array is just a A beautiful arrangement ：

perm[i] It can be i to be divisible by
i It can be perm[i] to be divisible by
Give you an integer n , Return constructable Beautifully arranged Of Number .

 source ： Power button （LeetCode）
 link ：https://leetcode.cn/problems/beautiful-arrangement
 Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

analysis

Back to the mind
Every number on the table does this , Traverse all numbers that can be divided by the current subscript or are divided by the current subscript , Then one bit forward and continue to traverse backward , Until each position has a number that meets the requirements .

class Solution {
    
    public int countArrangement(int n) {
    

    return dfs(n,1,1);
    }
    
    public int dfs(int n, int index, int visited) {
    
        if (index == n + 1){
    
            return 1;
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
    
            if ((index % i == 0 || i % index == 0) && (visited >> i & 1) == 0) {
    
                ans += dfs(n,index+1,visited | 1 << i);
            }
        }
        return ans;
    }
}