[LeetCode] 526. 优美的排列

题目描述：

假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：

• perm[i] 能够被 i 整除
• i 能够被 perm[i] 整除

给你一个整数 n ，返回可以构造的 优美排列 的 数量 。

示例 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

提示：

• 1 <= n <= 15

题目链接：

. - 力扣（LeetCode）

解题主要思路：

dfs暴力枚举即可，借助bool check[] 来记录是否遍历过该数字。当pos == n + 1时，代表遍历完了，递归结束。

解题代码：

class Solution {
public:
    int ret = 0;
    bool check[16];
    int countArrangement(int n) {
        dfs(1, n);
        return ret;
    }
    void dfs(int pos, int n)
    {
        // 递归结束条件
        if (pos == n + 1) {
            ++ret;
            return;
        }
        // 暴力枚举
        for (int i = 1; i <= n; ++i) {
            // 剪枝
            if (!check[i] && (i % pos == 0 || pos % i == 0)) {
                check[i] = true;
                dfs(pos+1, n);
                check[i] = false;  // 回溯
            }
        }
    }
};