题目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。
分析
回溯思想，题目明确说明N不会超过15，类似于暴力解法，但是带有剪枝策略，在第1-N个位置，依次放置数字，每个位置都尝试1-N，看是否合适，同时记录下这个数字使用的情况。如果不合适在当前位置直接换下一个数字，如果合适则有两种选择，第一在当前位置换一个数字尝试，第二继续回溯，当前位置使用这个数字，下一位置继续尝试1-N。
代码
class Solution {public:int countArrangement(int N) {used.resize(N + 1, false);BackTrace(N, 1);return ret;}int ret = 0;vector<bool> used;void BackTrace(int N, int idx) {if (idx > N) { // 所有位置都已经有合适的数字，结果加1ret += 1;return;}for (int i = 1; i <= N; ++i) {// 过滤掉不合适的数字和已经使用过的数字if (!used[i] && ((idx % i == 0) || (i % idx == 0))) {used[i] = true;BackTrace(N, idx + 1);used[i] = false;}}}};
