优美的排列Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件之一，该数组就是一个优美的排列：

perm[i] 能够被 i 整除
i 能够被 perm[i] 整除
给你一个整数 n ，返回可以构造的 优美排列 的 数量 。

示例 1：

输入：n = 2
输出：2
解释：
第 1 个优美的排列是 [1,2]：
    - perm[1] = 1 能被 i = 1 整除
    - perm[2] = 2 能被 i = 2 整除
第 2 个优美的排列是 [2,1]:
    - perm[1] = 2 能被 i = 1 整除
    - i = 2 能被 perm[2] = 1 整除

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 15

# 思路

//思路就是回溯法，与全排列等同
//DFS搜索，每前进一步，必须满足两个条件之一，分情况往下走(全排列问题)

# 解法


class Solution {
//思路就是回溯法，与全排列等同
//DFS搜索，每前进一步，必须满足两个条件之一，分情况往下走(全排列问题)

int count=0;

public int countArrangement(int N) {
    int[] visited=new int[N+1];
    countArrangement(1,N,visited);
    return count;
}
public void countArrangement(int step,int N,int[] visited)
{
    if(step==N+1)
    {
        count++;
        return;
    }
    for(int i=1;i<=N;i++)
    {
        //用过的不能再次使用，避免重复
        if(visited[i]==0)
        {
        visited[i]=1;
        //限制条件进行，剪枝
        if(i%step==0||step%i==0)
        {             
           countArrangement(step+1,N,visited); 
        }
        visited[i]=0;
        }
    }
    
}
}

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

# 总结

分析出几种情况，然后分别对各个情况实现