526. 优美的排列

问题

假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：

第 i 位的数字能被 i 整除
i 能被第 i 位上的数字整除
现在给定一个整数 N，请问可以构造多少个优美的排列？

示例1:

输入: 2
输出: 2
解释:

第 1 个优美的排列是 [1, 2]:
第 1 个位置（i=1）上的数字是1，1能被 i（i=1）整除
第 2 个位置（i=2）上的数字是2，2能被 i（i=2）整除

第 2 个优美的排列是 [2, 1]:
第 1 个位置（i=1）上的数字是2，2能被 i（i=1）整除
第 2 个位置（i=2）上的数字是1，i（i=2）能被 1 整除
说明:

N 是一个正整数，并且不会超过15。

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 调试版
public class Solution {
    int count = 0;
    public int countArrangement(int N) {
        boolean[] visited = new boolean[N + 1];
        calculate(N, 1, visited);
        return count;
    }
    public void calculate(int N, int pos, boolean[] visited) {
        if (pos > N)
            count++; // 为什么没有return ？
        for (int i = 1; i <= N; i++) {
            if (!visited[i] && (pos % i == 0 || i % pos == 0)) { // 与一般的全排列问题区别在于dfs的条件发生了改变
                visited[i] = true; // 修改状态变量
                
//                System.out.print("递归前：");
//                for (int j = 1; j < visited.length; ++j){
//                    System.out.print(visited[j] + " ");
//                }
//                System.out.println();
                
                calculate(N, pos + 1, visited); // dfs
                
//                System.out.print("递归后：");
//                for (int j = 1; j < visited.length; ++j){
//                    System.out.print(visited[j] + " ");
//                }
//                System.out.println();
                
                visited[i] = false; // 回溯，修改状态变量
            }
        }
    }
//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        int N = 3;
//        int count = solution.countArrangement(N);
//        System.out.println(count);
//    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
递归前：true false false 
递归前：true true false 
递归前：true true true 
递归后：true true true 
递归后：true true false 
递归后：true false false 
递归前：false true false 
递归前：true true false 
递归前：true true true 
递归后：true true true 
递归后：true true false 
递归后：false true false 
递归前：false false true 
递归前：true false true 
递归后：true false true 
递归前：false true true 
递归前：true true true 
递归后：true true true 
递归后：false true true 
递归后：false false true 
3

思考

  1. visited什么时候设为全局，什么时候设在dfs内的for前？