题目描述
思路解析动画文字版
记住这套「能放就放、放满计一种、放不下就回退换数」，下面每一帧都在套它。
上面一排是能用的数字 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题