全排列

回溯与搜索 · 决策树 DFS

列出所有排列

给一组互不相同的元素 [1, 2, 3]，列出它们的全部排列——即所有「谁在第 1 位、谁在第 2 位……」的顺序。n 个元素共有 n! = n × (n−1) × … × 1 个排列。这也是回溯的经典范例，和子集生成用的是同一套决策树可视化，只是决策的方式不同。

每个位置，从「剩下的」里挑一个

排列要求每个元素恰好用一次。所以在决策树上，每往下一层就为下一个位置从「还没用过」的元素里挑一个：根有 3 个选择（第 1 位放谁），选定后剩 2 个（第 2 位），再剩 1 个（第 3 位）——分支数逐层收窄 3 → 2 → 1，走到叶子（元素用光）就得到一个完整排列，3! = 6 个叶子对应 6 个排列。

这正是它和子集的对照：子集对每个元素做「选 / 不选」的二叉决策（元素可要可不要）；排列在每个位置「从剩余里挑一个」做多叉决策（元素必用且不重复）。回溯的骨架完全一样——选一个 → 递归到底 → 撤销换下一个。「已经用过的元素直接跳过」就是这里的剪枝。

下面是 [1, 2, 3] 的完整排列决策树。点「下一步」逐步看：当前节点琥珀高亮、根到当前的路径连起来高亮（此刻已挑的元素）；每条边标着这一步选了哪个元素；走到叶子就标绿、记录一个排列；一支走完就回溯去挑下一个剩余元素。右侧代码随每一步同步高亮。

空排列：每个位置从「剩余未用元素」里挑一个

1function permute(nums: number[]): number[][] {
const res: number[][] = [];
const cur: number[] = [];
const used = new Array(nums.length).fill(false);
const backtrack = (): void => {
  if (cur.length === nums.length) {
    res.push([...cur]);
    return;
  }
  for (let i = 0; i < nums.length; i++) {
    if (used[i]) continue;   // 跳过已用（剪枝）
    used[i] = true;
    cur.push(nums[i]);       // 选 nums[i]
    backtrack();
    cur.pop();               // 撤销（回溯）
    used[i] = false;
  }
};
backtrack();
return res;
21}

元素1 2 3

当前排列[]

剩余{1,2,3}

已收集0 / 6

1 / 28

注意分支数 3 → 2 → 1 相乘正好是 3! = 6——这就是排列数为 n! 的直观来源。实现上通常用一个 used[] 标记谁已用过：进入一层前把选中的标为已用、递归、回来再撤销标记（回溯），保证每个元素在一条根到叶的路径上只出现一次。

排列在哪里用

穷举顺序：旅行商暴力解、任务排期、密码/字典序枚举。
回溯家族：排列与子集、组合、组合总和同属「决策树 DFS」，区别只在每步的选择集与剪枝规则。
去重排列（含重复元素）只需在同层跳过重复选择——依旧是同一棵决策树上的剪枝。

至此回溯与搜索大类有了三种视角：N 皇后（棋盘约束）、子集（二叉决策树）、全排列（多叉决策树）——同一套 DFS + 剪枝 + 回退，套在不同的选择结构上。

算法可视化

全排列

列出所有排列

每个位置，从「剩下的」里挑一个

排列在哪里用