这题目看起来是真的有点迷，中级题目。

给一个从1到N的数组，对该数组进行重构，使之符合以下两条规则：

  1. 第i个数能够被i整除
  2. i能够被第i个整除

我们需要返回能够符合以上两条规则之一或者同时满足的数组的个数。0 < N <= 15

怎么说好呢，一个数组升序都是满足的。

emmmm 完全没有思路啊，，我看来得去看看MOOC上浙大的数据结构和北大的算法课。。

貌似可以用回溯，，回溯在大一时简直就是噩梦，都没有听懂。。。。

看了大佬的回溯算法，简直有点迷，递归回溯算法。。我先贴个码吧，我先去刷了慕课了。。

应该是用了递归深度搜索方法，仔细看看真的好妙 啊。

我还是多看看课程吧，算法渣。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution{
public:
    int coutArrangement(int N){
        int ans = 0;
        visited = vector<int>(N + 1, 0);
        dfs(N, &ans, 1); // 第 1 个数开始搜索
        return ans;
    }   
private:
    vector<int> visited;
    void dfs(int n, int *ans, int pos){
        if(pos > n){
            (*ans)++; // 找到了一个符合的数组
        }
        int i = 0; 
        for(int i = 1; i <= n; i++){
            if(!visited[i] && (i % pos == 0 || pos % i == 0)){
                visited[i] = 1; // 在深度搜索的时候，该位置无法被访问
                dfs(n, ans, pos + 1);
                visited[i] = 0; // 深层的深度搜索结束了，该位置恢复访问。。
            }
        }
    }
}