問題：

Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 ≤ i ≤ N) in this array:

1. The number at the ith position is divisible by i.
2. i is divisible by the number at the ith position.
   Now given N, how many beautiful arrangements can you construct?
   Example 1:

Input: 2
Output: 2
Explanation:
The first beautiful arrangement is [1, 2]:
Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).
Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).
The second beautiful arrangement is [2, 1]:
Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).
Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.

Note:

1. N is a positive integer and will not exceed 15.

大意：

假設(shè)你有1到N的N個整數(shù)，我們定義如果這N個整數(shù)可以組成數(shù)組后每第 i 位（1 ≤ i ≤ N）都滿足下面兩個要求之一就稱其為漂亮的安排：

1. 第 i 個位置的數(shù)字可以被 i 整除。
2. i 可以被第 i 個位置的數(shù)字整除扰魂。
   現(xiàn)在給出N鲁沥，你可以組成多少種漂亮的安排弟跑？
   例 1:

輸入： 2
輸出： 2
解釋：
第一個漂亮的安排是 [1, 2]：
第一個位置（i = 1）的數(shù)字是 1秘血，而 1 可以被 i （i = 1）整除胆建。
第二個位置（i = 2）的數(shù)字是 2驳庭，而 2 可以被 i（i = 2）整除。
第二個漂亮的安排是 [2, 1]：
第一個位置（i = 1）的數(shù)字是 2柔纵，而 2 可以被 i （i = 1）整除缔杉。
第二個位置（i = 2）的數(shù)字是 1，而 1 可以被 i（i = 2）整除搁料。

注意：

1. N是個正數(shù)或详，而且不會超過15。

思路：

乍一想有很多種可能不知道怎么統(tǒng)計(jì)郭计，而這恰恰就可以通過遞歸回溯來實(shí)現(xiàn)霸琴。

我們的思路是，從第一位到第N位昭伸，我們都要找到對應(yīng)的沒有放置過的數(shù)字來放梧乘，每一位都會有很多個數(shù)字可以放，而放了之后以后就不能放了，這樣一直放到最后一位选调，如果都能放到數(shù)字夹供，那就是一種漂亮的安排，總結(jié)果就要加一仁堪。

這種思路就可以通過遞歸來實(shí)現(xiàn)哮洽。每一次遞歸我們都判斷當(dāng)前位置有哪些沒放過的數(shù)字可以放，對于數(shù)字有沒有放過我們需要一個數(shù)字來記錄弦聂。對于每個放在這一位的數(shù)字鸟辅，都是一種可能性，我們要繼續(xù)往后遞歸看能不能全部放完才能知道要不要算作一種莺葫。如果所有都放完了那就算作一種了剔桨，總結(jié)過可以加一。

要注意這里的位置并不是從0開始算的徙融，而是1。

代碼（Java）：

public class Solution {
    public int countArrangement(int N) {
        int[] num = new int[N];
        int res = findWay(num, 1);
        return res;
    }
    
    public int findWay(int[] num, int index) {
        if (index == num.length+1) return 1;
        int total = 0;
        for (int i = 0; i < num.length; i++) {
            if (num[i] != 1) {
                if ((i+1) % index == 0 || index % (i+1) == 0) {
                    int[] newNum = num.clone();
                    newNum[i] = 1;
                    total += findWay(newNum, index+1);
                }
            }
        }
        return total;
    }
}

合集：https://github.com/Cloudox/LeetCode-Record

查看作者首頁