一.题目526. 优美的排列 - 力扣LeetCode二.思路讲解2.1 思路讲解本题要求计算从 1 到 n 的所有整数排列中满足“优美排列”条件的个数。优美排列的定义是对于排列中的每个位置i下标从 1 开始该位置上的数字perm[i]要么能被 i 整除要么 i 能被 perm[i] 整除。由于 n 最大为 15我们可以使用深度优先搜索DFS来枚举所有可能的排列并统计符合条件的个数。与前几道题不同本题的搜索过程中每一层可以选择任意一个未被使用过的数字而不是只能从某个固定起点开始。因此我们需要一个布尔数组check来标记每个数字是否已经被使用以避免重复。同时由于排列的下标从 1 开始递归函数的终止条件为pos n 1即已经处理完所有位置此时将计数加 1。在递归过程中对于当前位置pos我们遍历所有尚未使用的数字i1 到 n如果i与pos满足整除关系i % pos 0或pos % i 0则选择该数字标记为已使用然后递归下一位置pos1递归返回后恢复标记回溯继续尝试其他数字。三.代码演示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,pos1); check[i] false; } } } } };四.代码讲解一、全局变量设计为了实现回溯计数我们定义两个成员变量ret整型用于累计满足条件的优美排列个数初始为 0。check布尔数组大小为15因为 n ≤ 15check[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, pos1)继续填充下一个位置。递归返回后执行回溯将check[i]重新设为false以便尝试其他数字。四、关键细节下标从 1 开始题目中位置从 1 计数因此递归参数pos从 1 开始终止于n1。