题目描述
思路解析
一句话答案：LeetCode 526 优美的排列用回溯 DFS：逐位放数，位置 i 只试满足 i 整除 x 或 x 整除 i 的 x，放满 n 位计一种，整除剪枝砍掉大片分支。时间 O(n!)、空间 O(n²)。
优美排列到底在数满足整除的排法有几种
有 1 到 n 这 n 个整数，排成数组 perm，位置从 1 数起。只要每个位置都满足「perm[i] 能被 i 整除」或「i 能被 perm[i] 整除」其一，就叫优美排列。问一共能排出多少个优美排列。题面给 n=2 答案 2（[1,2] 和 [2,1] 都行），n=3 答案 3（[1,2,3]、[2,1,3]、[3,2,1]）。要的是总个数，不是某个排列。
为什么把 n 个数的全排列都摆出来会算不动
最直接是把全排列（1 到 n 的所有排法）都列出来，逐位检查整除条件，满足就计数。可 n 个数的全排列有 n! 个，n=15 就是一万三千亿个，光生成完就跑不动。而且大量排列在很靠前就已违规：首位放个和位置 1 对不上的数，后面怎么填都白填，笨办法却还要把这条死路铺满。违规能提前发现，就边填边判，某位放不下立刻掉头，不必等整条拼完。
一个位置能放哪些数，为什么两个整除方向都得判
位置 i 能放数字 x 的条件是 i 整除 x 或者 x 整除 i，满足一个就行。两个方向缺一不可——只判 x 整除 i（位置 2 只收 2、4、6…）会漏掉「i 整除 x」那半边，位置 1 能收所有数正是靠这一侧。参考代码先花 O(n²) 把关系表 match 建好：对每个位置 i 扫一遍 1 到 n，把满足 j%i==0 或 i%j==0 的数字 j 收进 match[i]。往后每到一位直接从候选表挑。
逐位放数、放完撤标记，回溯怎么做到不重不漏
从位置 1 起逐位往后放，这就是回溯（沿一条路径往下试，走不通就退回上一步换个选择）。到位置 i 时，遍历 match[i] 里还没用过的数字 j，用 vis 数组标记 j 已占用，再递归（函数自己调用自己，去处理下一位）填位置 i+1；等这条分支所有可能都试完、递归返回，立刻把 vis[j] 撤回没用过。这一撤是关键：不撤销，这个数字会被当成永久占用，别的分支就再用不上，会漏掉一大批合法排列。当位置填到 n+1，说明每位都合法放满，答案加一。
拿 n=3 亲手把三种优美排列搜出来
先建 match 表：位置 1 收 1、2、3；位置 2 收 1、2；位置 3 收 1、3。
位置 1 放 1：位置 2 只剩 2，位置 3 只剩 3，拼成 [1,2,3]，第 1 种。位置 1 放 2：位置 2 放 1、位置 3 放 3，得 [2,1,3]，第 2 种。位置 1 放 3：位置 2 若放 1，位置 3 的候选 1、3 全被占，走死回退；位置 2 改放 2、位置 3 放 1，得 [3,2,1]，第 3 种。三条起手搜完，答案 3，和题面对上。
回溯为什么不超时，撤销和从 1 起编号两个坑
搜索树（所有尝试分支长成的一棵树）最坏有 O(n!) 个节点，但整除条件剪掉大量分支，实际远小于上界，n=15 也就几万到几十万次，能过。空间主要是预存的 match 表 O(n²)，加 vis 数组和递归栈 O(n)。两个坑最容易踩：一是递归返回后忘撤销 vis 标记，数字被当永久占用，会少算很多排列；二是位置和数字都从 1 编号，从 0 起会让「i 整除 x」变成除以 0 出错。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套「能放就放、放满计一种、放不下就回退换数」，下面每一帧都在套它。
上面一排是能用的数字 1、2、3、4，下面 path 是正在拼的排列。规矩很简单：把数字 x 放进位置 i，要么 x 能整除 i，要么 i 能整除 x，满足一个就行。
位置 1 先放数字 1。任何数除以 1 都余 0，1 当然能整除位置 1，放下去。path 现在是 [1]。
来到位置 2。先看数字 1，可它已经放过了，变灰不能再用，跳过它。
再看数字 3：3 除以 2 余 1，2 除以 3 也除不尽，3 和位置 2 互相都整除不了，放不进来。
数字 2 还没用，而且 2 除以 2 余 0，正好整除位置 2，放进来。path 变成 [1, 2]。
位置 3：数字 1 已用跳过；数字 3 除以 3 余 0，能整除位置 3，放下去。path 变成 [1, 2, 3]。
位置 4：1、2、3 都用过了，只剩数字 4，4 除以 4 余 0，放进来。path 变成 [1, 2, 3, 4]。
四个位置全放满了，这就是一种优美的排列 [1, 2, 3, 4]，收进右边结果区。已经找到 1 种。
这条路走到底了，开始回退：位置 4、位置 3、位置 2 放的数字依次撤掉，path 缩回到只剩 [1]，回到位置 2 去换个别的数字。
位置 2 这次改放数字 4：4 除以 2 余 0，数字 4 能被位置 2 整除，放下去。path 变成 [1, 4]。
位置 3：1、4 都用过，候选里剩数字 3，3 除以 3 余 0，放进来。path 变成 [1, 4, 3]。
位置 4 只剩数字 2。这次反过来看：位置 4 除以数字 2 余 0，数字 2 能整除位置 4 也算数，放进来。path 变成 [1, 4, 3, 2]。
又放满了，这是第 2 种优美排列 [1, 4, 3, 2]，收进结果。已经找到 2 种。
位置 1 放 1 的所有分支都试完了，回到最开头，位置 1 改放数字 2，重新往后搜。
沿同一套规则往下放：位置 2 放 1（位置 2 除以 1 余 0），位置 3 放 3，位置 4 放 4，凑出第 3 种 [2, 1, 3, 4]。
回到位置 2 换成数字 4，再往下放，得到第 4 种 [2, 4, 3, 1]。已经找到 4 种。
位置 1 再换成数字 3，继续往后搜。
逐位套整除规则放下去，得到第 5 种 [3, 2, 1, 4]。
换条岔路再放，得到第 6 种 [3, 4, 1, 2]。已经找到 6 种。
位置 1 最后换成数字 4，把最后一类起手也搜一遍。
放出第 7 种 [4, 1, 3, 2]。
最后放出第 8 种 [4, 2, 3, 1]。
位置 1 的四种起手（1、2、3、4）全都搜过，回溯把每一种可能都走遍，右边正好攒了 8 种优美的排列。所以 n = 4 的答案就是 8。
小规模先手算验证：1 种、2 种、3 种，规律和搜索结果对得上。
两个高频追问：规模能过、以及可升级到状压 DP。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def countArrangement(self, n: int) -> int: def dfs(i): nonlocal ans, n if i == n + 1: ans += 1 return for j in match[i]: if not vis[j]: vis[j] = True dfs(i + 1) vis[j] = False ans = 0 vis = [False] * (n + 1) match = defaultdict(list) for i in range(1, n + 1): for j in range(1, n + 1): if j % i == 0 or i % j == 0: match[i].append(j) dfs(1) return ans复杂度
- 时间：O(n!)，搜索树节点数，最坏不超过 O(n!)；整除剪枝后实际远少
- 空间：O(n²)，match 表预存每个位置候选 O(n²) + vis 与递归栈 O(n)
易错点
面试追问把动画讲成自己的话
追问n 最大才 15，直接回溯会不会超时？
追问按位置放数字 和 按数字找位置，哪种写法更好？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
出界的路径数
LeetCode 576 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题