算法►回溯

排列型回溯

排列型回溯的本质是「每一层都可以从所有未使用的元素中重新选择」，顺序不同即视为不同答案，通常通过 used / flag 数组 来记录当前路径中已使用的元素。

一、什么是排列型回溯？

在回溯问题中，排列型问题有一个非常鲜明的特征：

  • 元素相同，但顺序不同，算作不同答案
  • 例如：
    • [1, 2] 和 [2, 1] 是 两个不同的解

这与我们之前做过的两类问题形成了清晰对比：

类型 是否关心顺序 是否允许重复选
子集型 ❌ 不关心 每个元素只选 / 不选
组合型 ❌ 不关心 对于选或不选有约束条件
排列型 ✅ 关心 每一轮可选任意当前轮次未使用元素

二、排列型回溯的核心思想

从「枚举答案的角度」来看，排列型回溯有两个关键点：

每一层都在“选位置”，而不是“选元素范围”

  • 第 0 位选谁？
  • 第 1 位选谁？
  • 第 2 位选谁？

每一层都可以从 当前轮所有尚未使用的元素中选择

必须显式记录「当前路径中已使用的元素」

因此，排列型回溯 一定需要 一个 used / flag 数组：

1
2
used[i] = true  → nums[i] 已经在当前排列中使用过
used[i] = false → 当前轮次仍可选择 nums[i]

三、基础题目分析

46. 全排列（Permutations）

问题特征

  • 目标：生成数组的所有排列
  • 终止条件：当前路径长度 == nums.length
  • 每一层：从所有 used[i] == false 的元素中选一个

核心实现思路

  1. 使用 path 记录当前排列
  2. 使用 used[] 标记哪些元素已被选
  3. 当 path.size() == nums.length 时，记录答案
  4. 回溯时恢复现场（used[i] = false）

关键点总结

  • 排列的深度 = nums.length
  • 叶子节点数量 = n!
  • used[] 的作用是：保证每个元素在同一条路径中只出现一次

51. N 皇后（N-Queens）

这是一个非常经典的“受限排列问题”。

问题拆解

  • 每一行只能放一个皇后
  • 每一列只能放一个皇后
  • 皇后不能在同一条对角线上

建模方式（非常关键）

用一个一维数组 queens 表示棋盘状态：

1
queens[row] = col

含义是：

  • 第 row 行
  • 第 col 列
  • 放置了一个皇后

为什么这是一个排列问题？

  • 行天然不重复（递归层数保证）
  • 列不能重复 → queens 本质是一个 列索引的全排列
  • 对角线限制 → 给这个全排列 增加合法性约束

对角线判断条件

若两个皇后在 (r1, c1) 和 (r2, c2)：

1
|r1 - r2| == |c1 - c2| → 在同一对角线

本质总结

N 皇后 = 带约束条件的全排列问题

四、扩展题目

357. 统计各位数字都不同的数字个数

这道题虽然形式不同，但本质仍然是：

  • 在每一位上选数字
  • 同一个数字不能重复使用
  • 位数不同，形成不同答案

本质是 多层排列 + 剪枝计数，而不是生成具体排列。

五、排列型回溯的时间复杂度

排列问题的时间复杂度通常非常直观：

  • 等于叶子节点数量

  • 对于 n 个元素的全排列：

    1
    时间复杂度 = O(n!) // 画树分析节点数量得到

这是排列问题不可避免的代价，因此：

  • 剪枝尤为重要
  • 约束条件越多，搜索空间越小

六、心得体会与方法论总结

排列型回溯的固定模板

  1. 路径长度固定（通常等于元素个数）
  2. 每一层从 所有未使用元素中选择
  3. 使用 used[] / flag[] 记录使用状态
  4. 回溯时一定要 恢复现场

与前两类回溯的根本区别

是否允许在下一层重新选择之前没选过的元素

  • 子集 / 组合：「之前轮次选过，就不能再选」
  • 排列：「只要当前路径没用过，就可以选」

相关代码

本文涉及的所有代码与笔记，均已同步至我的 GitHub 算法仓库，作为 Java 后端校招过程中的学习记录。