LeetCode Beautiful Arrangement 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 i_th position (1 ≤ i ≤ N) in this array:

1. The number at the i_th position is divisible by i.
2. i is divisible by the number at the i_th 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:

1. N is a positive integer and will not exceed 15.

---

本题要求1~N共有多少个漂亮的排列。一个漂亮的排列A[]需要满足以下两个条件中的一个：

1. A[i]能整除i
2. i能整除A[i]

上面的规则中下标从1开始。 本题使用DFS解决，想象数组长度为N，每个位置上都可能填入1~N这N个数。咱们从第一个位置，尝试填入1~N，然后把visited置位；第二个位置，尝试填入除第一个已经填入的其他所有数字。每个位置尝试填入时，都需要至少满足以上两个条件中的一个。当所有位置都填满时，找到一个可行解。回退时，需要把visited相关位复位。 完整代码如下： [cpp] class Solution { void dfs(int step, const int& N, vector<int>& visited, int& ans) { if (step > N) { ++ans; return; } for (int i = 1; i <= N; ++i) { if (visited[i] == 0 && (i%step == 0 || step%i == 0)) { visited[i] = 1; dfs(step + 1, N, visited, ans); visited[i] = 0; } } } public: int countArrangement(int N) { vector<int> visited(N + 1, 0); int ans = 0; dfs(1, N, visited, ans); return ans; } }; [/cpp] 本代码提交AC，用时149MS。]]>