优美排列如何用回溯计数？位置约束如何剪枝？

简化版

优美排列要求第 pos 个位置放的数字 num 满足：num % pos === 0 或 pos % num === 0。

用回溯按位置从 1 到 n 填数，维护哪些数字已经用过。

每个位置只尝试满足条件且未使用的数字，这就是剪枝。

详细版

递归状态是当前位置 pos 和使用标记 used。

如果 pos > n，说明已经填完一个合法排列，答案加 1。

否则枚举 1..n 中未使用的数字 num，只有当它和 pos 满足整除关系时，才放入当前位置并递归下一层。

这题本质是“带位置约束的全排列计数”。约束越早检查，剪枝越有效。

可以预处理每个位置可放的数字列表，减少递归时的判断成本。

完整版教学

一、为什么这是排列回溯

题目要把 1..n 的数字放进 1..n 个位置，每个数字只能用一次，这就是排列问题。不同的是普通全排列没有位置限制，而优美排列每个位置能放哪些数字由整除关系决定。因此它是“全排列 + 约束剪枝”的典型回溯。

记忆钩子：排列题先看 used，约束题尽早剪枝。

二、位置约束如何理解

对位置 pos 和候选数字 num，合法条件是：

num % pos === 0 || pos % num === 0

例如 pos = 3 时，可以放 1、3、6... 中未使用的数字；如果 n = 4，可选就是 1 和 3。越靠后的位置不一定选择越少，具体取决于因子和倍数关系。

位置	n=4 时可放数字
1	1,2,3,4
2	1,2,4
3	1,3
4	1,2,4

提前知道可选列表可以让搜索更清晰。

三、回溯状态怎么设计

递归函数 dfs(pos) 表示正在填第 pos 个位置。used[num] 表示数字 num 是否已经被放过。每层枚举当前可用数字，选择后标记，递归下一位置，返回时取消标记。

选择 num -> used[num]=true
递归 pos+1
撤销 num -> used[num]=false

这就是标准排列回溯的状态恢复。

四、代码模板

实现如下：

function countArrangement(n) {
  const used = new Array(n + 1).fill(false)
  let ans = 0

  function dfs(pos) {
    if (pos > n) {
      ans++
      return
    }
    for (let num = 1; num <= n; num++) {
      if (used[num]) continue
      if (num % pos !== 0 && pos % num !== 0) continue
      used[num] = true
      dfs(pos + 1)
      used[num] = false
    }
  }

  dfs(1)
  return ans
}

如果 n 较大，可以用位掩码表示 used，再配合记忆化优化。

五、剪枝为什么有效

普通全排列有 n! 个叶子。优美排列如果先生成全排列再检查，会浪费大量非法分支。把整除条件放在每个位置选择前，可以在树的上层直接剪掉不可能完成的路径。

先检查再递归：非法分支不再展开
先生成再检查：非法分支走到底才丢弃

剪枝的本质是提前发现约束冲突。

六、常见误区与追问

误区：下标从 0 开始直接套条件。 题目位置从 1 开始，不能用 0 参与取模。
误区：生成完整排列后再判断。 这样剪枝太晚，复杂度会明显变差。
误区：忘记恢复 used。 会导致兄弟分支误以为数字已被占用。
追问：能否用动态规划？ 可以用状态压缩 DP，状态是已使用数字集合。
追问：为什么 pos 从 1 到 n 填？ 位置约束直接依赖 pos，按位置填最自然。

这些问题考的是约束驱动的回溯设计。

七、加强记忆

优美排列记成“按位置填数，整除才进，used 回退”。每层处理一个位置，只尝试未使用且满足 num%pos==0 或 pos%num==0 的数字。它不是普通全排列后过滤，而是边构造边剪枝。位置从 1 开始是最容易踩的坑。

简化版

详细版