假设有从 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。

思路：

类似全排列的解法  就是看排列的结果是否满足题目意思  进行回溯法递归  先确定第一个位置  对之后位置进行递归  

    // 类似全排列的解法 回溯法子  相當於看排列的方式是否滿足條件
    int count = 0;
    public int countArrangement(int N) {
        if (N == 0) return 0;
        int[] arr = new int[N+1];
        for (int i = 0; i <= N; i++) arr[i] = i;
        getBeautifyCount(arr,1, N);  //1到n的位置
        return count;
    }
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    private void getBeautifyCount(int[] arr, int start, int n) {
        if (start > n) {
            count++;
            return;
        }
        //每次確定當前位置  後面的位置遞歸
        for (int i = start; i <= n; i++) { 
            swap(arr, start, i);   //交換  直到子递归结束
            if (arr[start] % start == 0 || start % arr[start] == 0) getBeautifyCount(arr, start+1,n);
            swap(arr,i, start);   //子递归结束   交換回來
        }
    }