hot100 全排列(46)

本题采用回溯状态搜索与置换空间穷举算法（又称“状态位拦截回溯法”）解决全排列组合生成问题。其核心本质是将一维无重复数组的所有排列情况抽象为深度为 n 的决策树的完全探测，通过布尔型状态数组进行路径冲突拦截。当前提供的源码实现了在时间复杂度 O(n * n!) 和额外空间复杂度 O(n) 条件下的决策树全盘扫描，最终走向是精准输出无重复整数数组的所有可能全排列集合。

一、 问题本质与数据模型

对于大小为 n 的无重复整数数组 nums，题目要求生成其所有可能的排列形态。该问题具备两个核心的数学和拓扑学特征：

  • 元素互异性与顺序相关性：每个排列必须完整包含 nums 中的所有元素，且相同元素的不同物理排放顺序被判定为不同的合法全排列形态。

  • 置换空间规模：由组合数学可证，包含 n 个不同元素的集合其全排列的绝对物理数量为 n!。

如果在搜索树的每一层推进中，仅仅盲目穷举数组的全部下标，会导致同一排列路径中出现重复提取相同元素的严重逻辑缺陷。

为了破除这种元素重复碰撞的退化困局，算法引入了“动态路径拦截模型”。通过维护一个与原数组等长且一一映射的布尔型状态数组onPath，实时记录当前搜索弹道上已被捕获的元素。当向下层探测时，循环遍历全数组，一旦检测到某位置的布尔标记为 true，则判定为冲突并直接执行剪枝拦截；只有未访问的节点才被准入，并在回溯时撤销标记以恢复全局物理现场，确保搜索空间的完备性与非重性。

二、 算法演进对比

在解决无重复序列全排列重组的场景中，状态数组回溯法在时空资源的控制上达到了平衡极限：

解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷
交换式回溯法 (Swap-based)O(n * n!)O(n)通过在原数组上直接交换元素位置实现全排列，规避状态标记无法维持生成序列的初期字典序，且频繁就地交换数组可能降低 CPU 缓存局部性
状态数组回溯法（当前解法）O(n * n!)O(n)引入辅助路径标记状态，依序组装列表，状态清晰直观每次命中叶子节点均需执行一次深度内存拷贝，对系统堆内存产生一定开销
非递归字典序演进法O(n * n!)O(1)基于当前排列，通过线性扫描寻找下一个字典序更大的置换形态编码存在复杂的逆序数查找与局部翻转控制，不适用于图/树状拓扑扩展

三、 核心分支控制逻辑与决策证明

当前源码的控制流完全依赖于回溯函数的深度推进参数i，以及内部基于布尔状态的for循环过滤器，其内部决策分支证明如下：

1. 叶子节点触发分支：if (i == nums.length)

  • 执行：ans.add(new ArrayList<>(path)); return;

  • 物理意义：深度参数i严格等于数组物理长度n，表明当前搜索弹道已成功下潜至决策树的最底层叶子节点。此时，path容器中已完美装载了一个合法的全排列变体。由于path是一个动态复用的单一引用，必须执行显式的全新实例化内存拷贝，才能将当前状态物理固化进结果集。

2. 路径冲突剪枝拦截：if (!onPath[j])

  • 执行：进入内层装配逻辑，否则直接隐式跳过（剪枝）。

  • 数学证明：当onPath[j]为 true 时，在拓扑上意味着下标为j的元素已经存在于从根节点到当前层级的活动路径上。根据全排列定义，同一个元素在单次置换序列中至多出现一次，因此该方向必须被强制物理排除。

3. 物理现场恢复（回溯）：onPath[j] = false; path.removeLast();

  • 执行：在下层递归dfs回溯返回后，同步执行状态反转与容器尾部元素移除。

  • 数学证明：在以当前节点为分支的子搜索树探测完毕后，为了保证平行并列的相邻分支能够公平且无偏差地重新检索该元素，必须将当前节点的占用状态物理抹除，实现搜索现场的完美复原。

四、 算法执行状态机步进示例

以输入数组nums = [1, 2, 3]为例（规模 n = 3，预期排列数 3! = 6），展示前两个排列生成的递归状态机步进过程：

步骤树深参数 i循环下标 j状态数组 onPath当前 path 容器内容执行的图遍历与回溯动作
初始00[false, false, false][]选取 nums[0]=1，onPath[0] 置为 true，推进至 i=1
110[true, false, false][1]扫描 j=0 冲突拦截；j=1 有效，选取 nums[1]=2，推进至 i=2
221[true, true, false][1, 2]j=0, 1 均冲突拦截；j=2 有效，选取 nums[2]=3，推进至 i=3
33-[true, true, true][1, 2, 3]满足 i==3 条件，执行克隆加入 ans，触发回溯，回退至 i=2
422[true, true, false][1, 2]清除 nums[2] 占用，j 循环完结，继续向后回溯至 i=1
511[true, false, false][1]清除 nums[1] 占用，循环继续推进，j 变为 2
612[true, false, true][1, 3]选取 nums[2]=3，进入另一平行分支，推进至 i=2
721[true, true, true][1, 3, 2]j=1 有效，选取 nums[1]=2，推进至 i=3，触发第二次命中

五、 源码实现

import java.util.ArrayList; import java.util.List; class Solution { public List<List<Integer>> permute(int[] nums) { // 初始化全局排列结果存放集 List<List<Integer>> ans = new ArrayList<>(); // 初始化单条排列路径的复用动态容器 List<Integer> path = new ArrayList<>(); // 实例化与输入等长的物理状态布尔数组，充当路径探测拦截器 boolean[] onPath = new boolean[nums.length]; // 启动回溯深度优先搜索，从树的第 0 层（根节点）开始演进 dfs(ans, path, nums, onPath, 0); // 返回完全收敛的全排列拓扑集合 return ans; } private void dfs(List<List<Integer>> ans, List<Integer> path, int[] nums, boolean[] onPath, int i) { // 基准收敛条件：树深指标等于数组总长度，说明成功捕获一条完整且合法的排列弹道 if (i == nums.length) { // 执行深度内存拷贝，固化当前排列状态至结果集中 ans.add(new ArrayList<>(path)); return; } // 循环扫描数组中所有潜在的物理元素位置 for (int j = 0; j < nums.length; j++) { // 动态拦截机制：只有当该位置的元素尚未被当前搜索路径占用时，方可准入 if (!onPath[j]) { onPath[j] = true; // 锁定物理位置状态 path.add(nums[j]); // 将数据元素注入路径尾部 // 向决策树的下一层级压栈递归推进 dfs(ans, path, nums, onPath, i + 1); // 现场恢复控制（回溯）：解除物理位置占用，以便平行分支重新检索 onPath[j] = false; // 弹出尾部元素，恢复单路径复用容器的原始物理面貌 path.removeLast(); } } } }

六、 复杂度分析

1. 时间复杂度：O(n * n!)

  • 分析：算法的核心是在一棵完全排列树上进行深度优先搜索。该决策树的叶子节点物理总量等于完全置换数 n!。在从根节点到任意一个叶子节点的路径推进中，所触发的有效for循环分支尝试次数受阶乘规律控制。更关键的是，每当搜索弹道下潜至叶子节点（触发基准条件）时，算法均会执行new ArrayList<>(path)操作，这一内存物理克隆行为所需的开销与当前排列长度 n 呈严格的线性正比关系。

  • 结论：总的基本原子操作步数完全被约束在 n 的阶乘与单次复制复杂度的乘积区间内，表现为 O(n * n!)。

2. 空间复杂度：O(n)

  • 分析：若排除用于存储最终全局结果集的ans容器所需的外部空间，算法在运行期间的动态内存开销完全由三部分组成：第一是系统进行深度优先探测时，运行时方法栈的并行最大深层帧数，严格受控于树高 n；第二是长度固定为 n 的布尔状态拦截矩阵onPath；第三是单条动态复用路径的path容器，其内部最大并存元素量为 n。

  • 结论：所有内部辅助分配的物理内存大小均不随置换组合的爆发现象而呈阶乘级扩张，额外空间复杂度被锁定在常数倍的线性阶 O(n)。