Problem
Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 ≤ i ≤ N) in this array:
The number at the ith position is divisible by i.
i is divisible by the number at the ith position.
Now given N, how many beautiful arrangements can you construct?
Example 1:
Input: 2
Output: 2
Explanation:
The first beautiful arrangement is [1, 2]:
Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).
Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).
The second beautiful arrangement is [2, 1]:
Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).
Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.
Note:
N is a positive integer and will not exceed 15.
题意
输入整数N，表示有N个数需要放置在N个位置上（数字和位置的下标都是从1到N），如果能够找出一个序列中任意一个数都满足以下两个条件中的一个，则将这个序列称为一个Beautiful Arrangement：
- arr[i]能够被i整除，i = 1, 2, ..., N
- i能够被arr[i]整除，i = 1, 2, ..., N
对于给出的N，要求计算出共有多少种Beautiful Arrangement.
分析
简单分析该题可以发现，将N个数字放置在N个位置上，这样的问题是较为典型的回溯问题：假设前i个数字已经放置好（满足条件1或条件2），则对于第i+1个位置，如果能从还未被放置的数字集合unused（或visited）中找到一个满足条件的数字k，则将其放在第i+1个位置，同时将k从unused中去掉（或者将visited[k - 1]标记为true），继续对第i+2执行相同的操作（通过递归调用）；如果找不到满足条件的数字，则回溯到上一层，修改第'i'个位置的数字，再尝试第'i+1'个位置···依此类推。
递归的base case应当是递归树的高度达到了N，如果当前层次为第N层，则表示从0到N-1层得到的这条路径是一个Beautiful Arrangement，count++。
Code
对于回溯同样也有不同的实现，下面贴出两段代码，都用到了回溯的思想，但在具体的实现上有所不同。
使用visited
//主要的思想是从后向前开始递归，即递归树的根节点是最后一个元素
//使用visited数组标识数字i是否已经被使用过
//Runtime: 19ms
class Solution {
private:
vector<bool> visited;
int count;
void _dfs(int N, int nextPos){
if (nextPos == 0){
count++;
return;
}
for (int i = 1; i <= N; i++){
//该数字已经被使用 || 两个条件都不满足
if (visited[i - 1] || nextPos % i != 0 && i % nextPos != 0)
continue;
visited[i - 1] = true;
//深入
_dfs(N, nextPos - 1);
//回溯
visited[i - 1] = false;
}
}
public:
int countArrangement(int N){
count = 0;
visited.resize(N);
for (int i = 0; i < N; i++) visited[i] = false;
_dfs(N, N);
return count;
}
};
使用swap
//这是Solution中效率很高的一份代码，贴在这里以供学习
//同样是从后向前，这个解法的作者使用swap函数代替了visited数组，主要思路如下：
//1. 初始化一个数组容器v，存放的元素为[1...N]（不包括0）
//1. 假设后面的下标从p+1到N-1的位置都已经放置好，考虑下标为p的位置
//2. for(int i = 0; i < p; i++) 遍历从v[0]到v[p-1]的数，如果v[i]满足条件，则将v[i]与v[p-1]交换
//3. 再次递归时，需要考虑的就只是下标从0到p-1的位置该如何放置了
//4. 返回结果时，再将v[i]与v[p-1]交换回来
//Runtime: 6ms
class Solution {
private:
int _count(int n, vector<int>& v){
if (n <= 1) return 1;
int result = 0;
for (int i = 0; i < n; i++){
if (v[i] % n == 0 || n % v[i] == 0){
swap(v[i], v[n - 1]);
result += _count(n - 1, v);
swap(v[i], v[n - 1]);
}
}
return result;
}
public:
int countArrangement(int N) {
vector<int> v;
v.resize(N);
for (int i = 0; i < N; i++) v[i] = i + 1;
return _count(N, v);
}
};
