深搜练习(优美的排列)(9)

一.题目

526. 优美的排列 - 力扣（LeetCode）

二.思路讲解

2.1 思路讲解

本题要求计算从 1 到 n 的所有整数排列中，满足“优美排列”条件的个数。优美排列的定义是：对于排列中的每个位置i（下标从 1 开始），该位置上的数字perm[i]要么能被 i 整除，要么 i 能被 perm[i] 整除。由于 n 最大为 15，我们可以使用深度优先搜索（DFS）来枚举所有可能的排列，并统计符合条件的个数。

与前几道题不同，本题的搜索过程中，每一层可以选择任意一个未被使用过的数字，而不是只能从某个固定起点开始。因此，我们需要一个布尔数组check来标记每个数字是否已经被使用，以避免重复。同时，由于排列的下标从 1 开始，递归函数的终止条件为pos == n + 1（即已经处理完所有位置），此时将计数加 1。

在递归过程中，对于当前位置pos，我们遍历所有尚未使用的数字i（1 到 n），如果i与pos满足整除关系（i % pos == 0或pos % i == 0），则选择该数字，标记为已使用，然后递归下一位置pos+1；递归返回后，恢复标记（回溯），继续尝试其他数字。

三.代码演示

class Solution { public: int ret; bool check[15]; int countArrangement(int n) { dfs(n,1); return ret; } void dfs(int n,int pos) { //1.递归出口 if(pos == n + 1) { ret++; return; } for(int i = 1;i <= n;i++) { //判断这个数是否用过了 if(check[i] == false) { //判断这个数符不符合优美数的定义 if(i % pos == 0 || pos % i == 0) { check[i] = true; dfs(n,pos+1); check[i] = false; } } } } };

四.代码讲解

一、全局变量设计

为了实现回溯计数，我们定义两个成员变量：

• ret：整型，用于累计满足条件的优美排列个数，初始为 0。

• check：布尔数组，大小为15（因为 n ≤ 15），check[i]表示数字i是否已经被当前排列使用。初始全为false。

二、主函数countArrangement

主函数接收整数n，调用递归函数dfs(n, 1)开始深度优先搜索，最后返回ret。参数pos表示当前正在填充的位置（下标从 1 开始）。

三、递归函数dfs

递归函数dfs(int n, int pos)的含义是：已经为前pos-1个位置填入了数字（且满足优美条件），接下来需要为第pos个位置选择数字。执行流程如下：

1. 递归终止条件

当pos == n + 1时，说明已经成功填满了所有 n 个位置，得到了一个完整的优美排列。此时将ret加 1，并返回。

2. 遍历数字并尝试放置

使用for循环遍历所有数字i从 1 到 n，依次尝试将其放入当前位置pos。只有满足以下条件才能选择：

• 该数字未被使用（check[i] == false）。

• 该数字与当前位置满足整除关系：i % pos == 0 || pos % i == 0（优美排列定义）。

如果条件满足，则：

• 将check[i]标记为true，表示该数字已被使用。

• 递归调用dfs(n, pos+1)，继续填充下一个位置。

• 递归返回后，执行回溯：将check[i]重新设为false，以便尝试其他数字。

四、关键细节

• 下标从 1 开始：题目中位置从 1 计数，因此递归参数pos从 1 开始，终止于n+1。