LeetCode刷题实战526： 优美的排列
Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n), either of the following is true:
perm[i] is divisible by i.
i is divisible by perm[i].
Given an integer n, return the number of the beautiful arrangements that you can construct.
perm[i] 能够被 i 整除
i 能够被 perm[i] 整除
示例
示例 1：
输入：n = 2
输出：2
解释：
第 1 个优美的排列是 [1,2]：
- perm[1] = 1 能被 i = 1 整除
- perm[2] = 2 能被 i = 2 整除
第 2 个优美的排列是 [2,1]:
- perm[1] = 2 能被 i = 1 整除
- i = 2 能被 perm[2] = 1 整除
示例 2：
输入：n = 1
输出：1
解题
class Solution {
public:
int res = 0;
int n;
vector<bool> visited; // 判断某个数字是否已经在当前排列出现过
void dfs(int u, vector<bool>& visited) {
if(u == n + 1) { // 找到一个满足条件的排列，答案++
++res;
return ;
}
for(int i = 1; i <= n; ++i) {
if(visited[i] == false && ((u % i == 0) || (i % u == 0))) { // 当前数字没有排列中出现过，且满足题目要求的条件，则尝试在当前位置放上数字i，再继续搜索下一个位置
visited[i] = true;
dfs(u + 1, visited);
visited[i] = false;
}
}
}
int countArrangement(int N) {
n = N;
visited = vector<bool>(n + 1, false);
dfs(1, visited);
return res;
}
};