題目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;}}}};
