本题采用回溯状态搜索与置换空间穷举算法又称“状态位拦截回溯法”解决全排列组合生成问题。其核心本质是将一维无重复数组的所有排列情况抽象为深度为 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]1onPath[0] 置为 true推进至 i1110[true, false, false][1]扫描 j0 冲突拦截j1 有效选取 nums[1]2推进至 i2221[true, true, false][1, 2]j0, 1 均冲突拦截j2 有效选取 nums[2]3推进至 i333-[true, true, true][1, 2, 3]满足 i3 条件执行克隆加入 ans触发回溯回退至 i2422[true, true, false][1, 2]清除 nums[2] 占用j 循环完结继续向后回溯至 i1511[true, false, false][1]清除 nums[1] 占用循环继续推进j 变为 2612[true, false, true][1, 3]选取 nums[2]3进入另一平行分支推进至 i2721[true, true, true][1, 3, 2]j1 有效选取 nums[1]2推进至 i3触发第二次命中五、 源码实现import java.util.ArrayList; import java.util.List; class Solution { public ListListInteger permute(int[] nums) { // 初始化全局排列结果存放集 ListListInteger ans new ArrayList(); // 初始化单条排列路径的复用动态容器 ListInteger path new ArrayList(); // 实例化与输入等长的物理状态布尔数组充当路径探测拦截器 boolean[] onPath new boolean[nums.length]; // 启动回溯深度优先搜索从树的第 0 层根节点开始演进 dfs(ans, path, nums, onPath, 0); // 返回完全收敛的全排列拓扑集合 return ans; } private void dfs(ListListInteger ans, ListInteger 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)。