526. Beautiful Arrangement

问题：

给定1～N，N个数，对他们进行排列

对一个排列中的每个数：

若第i个数p[i]能被 i 整除，或者 i 能被第i个数p[i] 整除，那么成为最优排列。

请问这样的最优排列有多少个。

Example 1:
Input: n = 2
Output: 2
Explanation: 
The first beautiful arrangement is [1,2]:
    - perm[1] = 1 is divisible by i = 1
    - perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
    - perm[1] = 2 is divisible by i = 1
    - i = 2 is divisible by perm[2] = 1

Example 2:
Input: n = 1
Output: 1
 

Constraints:
1 <= n <= 15

解法：Backtrack（回溯算法）

当前状态：从第一个位置到当前位置上，已经选择好的数组。
选择：1～N中满足：还未被选择 && 当前位置pos和该数字互相（任意方向）能整除。
退出递归条件：
- 　　当前位置>N

♻️ 优化：

由于1～N连续有限的数字特征，可联想到数字映射index。

当前状态path，可使用used数组标记那些数字已被使用替代。

代码参考：

 1 class Solution {
 2 public:
 3     void backtrack(int& res, vector<int>& used, int N, int pos) {
 4         if(pos > N) {
 5             res++;
 6             return;
 7         }
 8         for(int i=1; i<=N; i++) {
 9             if(used[i]==0 && (pos%i==0 || i%pos==0)) {
10                 used[i]=1;
11                 backtrack(res, used, N, pos+1);
12                 used[i]=0;
13             }
14         }
15         return;
16     }
17     int countArrangement(int N) {
18         int res=0;
19         vector<int> used(N+1,0);
20         backtrack(res, used, N, 1);
21         return res;
22     }
23 };