2017-10-03 14:33:00      个评论    来源：obrcnh的博客

## 题目

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 pisible by i.
i is pisible by the number at the ith position.
Now given N, how many beautiful arrangements can you construct?

Example:
Input: 2
Output: 2
Explanation:
The first beautiful arrangement is [1, 2]:
Number at the 1st position (i=1) is 1, and 1 is pisible by i (i=1).
Number at the 2nd position (i=2) is 2, and 2 is pisible by i (i=2).
The second beautiful arrangement is [2, 1]:
Number at the 1st position (i=1) is 2, and 2 is pisible by i (i=1).
Number at the 2nd position (i=2) is 1, and i (i=2) is pisible by 1.

### 源代码

```class Solution {
public:
int number = 0;

int countArrangement(int N) {
int* nums = new int[N + 1];
for (int i = 0; i <= N; i++) {
nums[i] = i;
}
count(nums, N);
return number;
}

void count(int* nums, int n) {
if (n == 0) {
number++;
return;
}
for (int i = n; i > 0; i--) {
swap(nums[i], nums[n]);
if (nums[n] % n == 0 || n % nums[n] == 0) {
count(nums, n - 1);
}
swap(nums[n], nums[i]);
}
}
};```