回溯生成：从空排列长出选择树
下一个排列是「一个接一个」地走；回溯 (backtracking) 则换一个视角看同一批排列：从空排列开始，逐位选一个还没用过的数填进去，填满即得一个排列；一个分支试完就撤销（回溯） 去试别的。把所有选择画出来，就是一棵选择树——根是空，每向下一层固定一位，每片叶子恰好是一个完整排列。
本页沿这棵树深度优先地单步展开，看「选 → 递归 → 撤销」如何系统地铺满全部 n! 片叶子。
核心是「选 → 递归 → 撤销」三连。 在某一位选定一个数后，把它标记为已用并递归去填下一位；当这条路探到底（或试完）回来时，必须撤销刚才的选择——把数从部分排列里弹出、重新标记为可用——才能公平地尝试同一位上的其他候选。撤销这一步，就是 backtracking 这个名字的来历。
叶子的顺序也是字典序。 只要每一位都按从小到大试候选（上面的 v = 1 .. n），深度优先到达叶子的先后就与反复调用 next 得到的字典序完全一致——两条看似不同的生成路线殊途同归。
这套骨架远不止排列。 把「填一位 + used 约束」换成别的「做一个选择 + 合法性检查」，同一份「选 → 递归 → 撤销」就变成 N 皇后、数独、子集 / 组合枚举、表达式求解…… 排列只是回溯法最干净的入门模型。更系统的搜索 / 剪枝见搜索系列。