假设有从 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
解题思路：回溯 + 剪枝
首先这道题我一开始就掉进一个坑，代码基本是正确的，但是因为题目漏了细节：只要满足优美排列的条件之一即可！我以为两个条件都得满足，导致花费了很长时间思考，所以审题很重要……
其实这道题并不难，是一个排列问题，就是要我们找到不同顺序的满足 n 个元素的数组，判断它是否为优美的排列，如果我们是到了叶子节点，然后遍历排列结果去判断是否为优美的排列的话，其实是非常麻烦的，所以我们可以考虑边遍历边判断！
就是当我们遍历到一个元素的时候，此时我们只要有当前构造到数组的尾部下标的话，就可以判断是否满足优美的排序，如果不是的话直接跳过该元素的选择即可达到剪枝的效果，所以我们需要在递归函数中多加一个参数 tail 表示当前构造到数组的尾部下标，它从下标 1 开始计算！而其实有了这个下标，我们边遍历边判断的话，其实就可以省略数组空间来存放叶子节点了，因为我们在遍历途中已经完成了判断！
然后因为是排列问题，所以需要有一个 used 数组来标记哪个元素已经走过了，防止重复，我们还是老样子，将其设为全局变量即可！
剩下的就是递归函数出口问题，当我们构造的数组下标超过 n 个的时候，此时因为前面已经是筛选过满足要求的元素了，现在还超过了 n 个，说明这是满足要求的结果，则让 ret++ 然后进行返回即可！
class Solution {
private:
int ret; // 结果集
bool used[16]; // 标记哪个元素已经走过，防止重复
public:
int countArrangement(int n) {
dfs(n, 1);
return ret;
}
// tail表示当前构造到数组的尾部下标，从1开始
void dfs(int n, int tail)
{
// 递归函数出口
if(tail > n)
{
ret++;
return;
}
for(int i = 1; i <= n; ++i)
{
// 剪枝
if((used[i] == true) || ((i % tail != 0) && (tail % i != 0)))
continue;
used[i] = true;
dfs(n, tail + 1);
used[i] = false;
}
}
};