Java版LeetCode热题100之全排列：回溯算法的深度剖析与实战指南

Java版LeetCode热题100之全排列：回溯算法的深度剖析与实战指南

摘要：本文将全面解析 LeetCode 热题 100 中的经典回溯问题——全排列（Permutations）。我们将从题目出发，深入探讨回溯算法的核心思想、递归结构设计、状态管理技巧，并提供两种高质量的 Java 实现方案。文章涵盖时间/空间复杂度分析、常见面试问题、实际应用场景、相关题目推荐等模块，帮助读者不仅“会做题”，更能“懂原理、能拓展、可应用”。

一、原题回顾

题目名称：全排列
题目编号：LeetCode 46
难度等级：中等

题目描述

给定一个不含重复数字的数组nums，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例

示例 1： 输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例 2： 输入：nums = [0,1] 输出：[[0,1],[1,0]] 示例 3： 输入：nums = [1] 输出：

提示

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums中的所有整数互不相同

二、原题分析

全排列问题是组合数学中的基础问题：给定 n 个不同元素，求出它们所有可能的排列方式。对于 n 个元素，共有n!种排列。

本题的关键约束是：

• 元素无重复
• 每个元素在每种排列中恰好出现一次
• 输出顺序任意

由于n ≤ 6，最大排列数为6! = 720，属于可枚举范围，因此适合使用**回溯法（Backtracking）**进行穷举。

⚠️ 注意：若数组含重复元素（如 LeetCode 47），则需额外去重处理，本题因无重复，简化了问题。

三、答案构思

3.1 回溯法的核心思想

回溯法是一种系统化地搜索所有可能解的算法，常用于组合、排列、子集等问题。其核心思想是：

“试错 + 撤销”—— 尝试一种选择，若无法得到解，则撤销该选择，尝试下一种。

回溯法通常通过递归实现，具有以下特征：

• 路径（Path）：已做出的选择
• 选择列表（Choices）：当前可做的选择
• 结束条件（Base Case）：到达决策树的叶子节点

对于全排列问题：

• 路径：当前正在构建的排列（如[1, 3]）
• 选择列表：尚未使用的数字
• 结束条件：路径长度等于nums.length

3.2 两种实现策略

官方题解提供了两种主流方法：

方法一：使用布尔数组标记已选元素

• 维护boolean[] used标记哪些元素已被使用
• 每层递归遍历所有元素，跳过已使用的
• 优点：逻辑清晰，易于理解
• 缺点：额外 O(n) 空间

方法二：原地交换（In-place Swapping）

• 将数组分为两部分：[0, first-1]已确定，[first, n-1]待选择
• 通过交换first与i（i ≥ first）来“选择”元素
• 回溯时再交换回来，恢复状态
• 优点：节省空间，无需额外标记数组
• 缺点：输出顺序非字典序（但题目允许任意顺序）

本文将重点讲解方法二（原地交换），因其更高效且体现了回溯的“状态恢复”精髓。

四、完整答案（Java 实现）

4.1 方法一：使用布尔数组（辅助理解）

classSolution{publicList<List<Integer>>permute(int[]nums){List<List<Integer>>result=newArrayList<>();List<Integer>path=newArrayList<>();boolean[]used=newboolean[nums.length];backtrack(nums,path,used,result);returnresult;}privatevoidbacktrack(int[]nums,List<Integer>path,boolean[]used,List<List<Integer>>result){// 结束条件：路径长度等于数组长度if(path.size()==nums.length){result.add(newArrayList<>(path));// 深拷贝return;}// 遍历所有选择for(inti=0;i<nums.length;i++){if(used[i])continue;// 跳过已使用的// 做选择path.add(nums[i]);used[i]=true;// 递归backtrack(nums,path,used,result);// 撤销选择（回溯）path.remove(path.size()-1);used[i]=false;}}}

4.2 方法二：原地交换（推荐，空间更优）

classSolution{publicList<List<Integer>>permute(int[]nums){List<List<Integer>>result=newArrayList<>();List<Integer>output=newArrayList<>();// 将数组转为 List，便于交换for(intnum:nums){output.add(num);}backtrack(output,result,0);returnresult;}privatevoidbacktrack(List<Integer>output,List<List<Integer>>result,intfirst){intn=output.size();// 结束条件：first 到达末尾if(first==n){result.add(newArrayList<>(output));// 深拷贝当前排列return;}// 尝试将 [first, n-1] 中的每个元素放到 first 位置for(inti=first;i<n;i++){// 做选择：交换 first 和 iCollections.swap(output,first,i);// 递归处理下一个位置backtrack(output,result,first+1);// 撤销选择：交换回来（关键！）Collections.swap(output,first,i);}}}

✅ 两种方法均可通过 LeetCode 测试。方法二更优，因其空间复杂度更低（无需used数组）。

五、代码分析

5.1 方法二的核心逻辑

递归函数backtrack(output, result, first)

• 参数含义：

  • output：当前排列（动态变化）
  • result：结果集
  • first：当前要确定的位置（从 0 开始）

• 递归过程：

  1. 若first == n，说明已确定所有位置，将当前output加入结果
  2. 否则，遍历i从first到n-1：
     • 选择：将output[i]放到first位置（通过交换）
     • 递归：处理first + 1位置
     • 撤销：交换回来，恢复output状态

为什么交换能保证正确性？

• 初始时，[0, first-1]是已固定的前缀
• 通过交换first与i，将output[i]“选中”作为第first个元素
• 递归结束后，必须交换回来，否则会影响后续分支的状态

🔑回溯的精髓在于“状态恢复”。若不撤销操作，后续递归将基于错误的状态进行，导致结果错误或遗漏。

5.2 深拷贝的重要性

result.add(newArrayList<>(output));

• 必须使用new ArrayList<>(output)创建副本
• 若直接result.add(output)，所有结果将指向同一个List对象
• 最终result中所有排列都会等于最后一次output的状态（通常是原数组）

5.3 边界情况处理

• nums.length == 1：直接返回[[nums[0]]]
• 空数组？题目规定length ≥ 1，无需处理

六、时间复杂度与空间复杂度分析

6.1 时间复杂度：O(n × n!)

这是全排列问题的理论下限，原因如下：

• 排列总数：n 个不同元素的全排列数为n!
• 每种排列的构建成本：需要 O(n) 时间复制到结果集
• 递归调用次数：虽然内部循环次数随深度减少，但总调用次数仍为 O(n!)

更精确的分析：

• 第 0 层：1 次调用
• 第 1 层：n 次调用
• 第 2 层：n × (n-1) 次调用
• …
• 第 n 层：n! 次调用（叶节点）

总调用次数 =1 + n + n(n-1) + ... + n! < 3 × n!（几何级数上界）

因此，时间复杂度为 O(n × n!)，无法优化（因为必须输出所有排列）。

6.2 空间复杂度：O(n)

• 递归栈深度：最多 n 层（first从 0 到 n）
• 每层栈空间：O(1)（仅存储局部变量）
• 结果集空间：O(n × n!)，但通常不计入空间复杂度（题目要求输出）
• 额外空间：
  • 方法一：used数组 O(n)
  • 方法二：无额外标记数组，仅 O(1) 临时变量

📌标准答案的空间复杂度为 O(n)（仅考虑算法运行所需额外空间，不含输出）。

七、常见问题解答（FAQ）

Q1: 为什么方法二不需要used数组？

答：通过数组分区隐式管理状态：

• [0, first-1]：已确定的元素（相当于“已使用”）
• [first, n-1]：待选择的元素（相当于“未使用”）
• 交换操作确保每次只从“未使用”部分选元素

Q2: 输出顺序为什么不是字典序？

答：方法二的遍历顺序由交换决定。例如[1,2,3]：

• 先固定 1 → 生成[1,2,3], [1,3,2]
• 再固定 2（交换后数组变为[2,1,3]）→ 生成[2,1,3], [2,3,1]
• 最后固定 3 → 生成[3,1,2], [3,2,1]

若需字典序，应使用方法一 + 按索引顺序遍历，或对结果排序。

Q3: 如何处理含重复元素的全排列（LeetCode 47）？

答：需在回溯时跳过重复选择：

1. 先对nums排序
2. 在循环中，若nums[i] == nums[i-1]且nums[i-1]未被使用，则跳过
3. 或使用Set记录当前层已选的值

Q4: 能否用迭代（非递归）实现？

答：可以，但复杂度高。常用方法：

• 使用栈模拟递归
• 基于字典序生成下一个排列（如 C++next_permutation）
• 但回溯法更直观，面试推荐递归写法

八、优化思路

8.1 空间优化：避免 List 转换

方法二中将int[]转为List<Integer>是为了使用Collections.swap。可改用原生数组交换：

privatevoidbacktrack(int[]nums,List<List<Integer>>result,intfirst){if(first==nums.length){// 手动转换为 ListList<Integer>perm=newArrayList<>();for(intnum:nums)perm.add(num);result.add(perm);return;}for(inti=first;i<nums.length;i++){swap(nums,first,i);backtrack(nums,result,first+1);swap(nums,first,i);}}privatevoidswap(int[]arr,inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}

优点：避免ArrayList的装箱/拆箱开销
缺点：每次添加结果需 O(n) 转换

8.2 性能优化：预分配结果集大小

已知结果数量为n!，可预先设置ArrayList容量：

intfactorial=1;for(inti=2;i<=nums.length;i++)factorial*=i;List<List<Integer>>result=newArrayList<>(factorial);

避免动态扩容的内存拷贝开销。

8.3 并行化？不推荐！

• 全排列问题天然串行（状态依赖）
• n ≤ 6时，单线程已足够快
• 并行 overhead 远大于收益

九、数据结构与算法基础知识点回顾

9.1 什么是回溯算法？

• 定义：一种通过递归+剪枝系统搜索解空间的算法
• 适用场景：组合、排列、子集、N皇后、数独等
• 核心要素：
  • 选择（Choose）
  • 约束（Constraint）
  • 目标（Goal）

9.2 回溯 vs DFS

回溯可视为带状态恢复的 DFS。

9.3 排列 vs 组合 vs 子集

9.4 决策树模型

全排列的决策树如下（以[1,2,3]为例）：

[] / | \ [1] [2] [3] / \ / \ / \ [1,2] [1,3] [2,1] [2,3] [3,1] [3,2] | | | | | | [1,2,3] [1,3,2] ...（共6个叶节点）

• 树深度：n
• 叶节点数：n!
• 回溯 = 从根到叶的路径探索 + 返回

十、面试官提问环节（模拟）

Q1: 请手写全排列，并解释回溯的过程。

答：（写出方法二代码后解释）

• 我们用first表示当前要确定的位置
• 对每个i >= first，将nums[i]放到first位置（交换）
• 递归处理first+1
• 返回后交换回来，尝试下一个i
• 当first == n时，得到一个完整排列

Q2: 时间复杂度为什么是 O(n × n!)？能否优化？

答：

• 共有n!个排列，每个需 O(n) 时间复制 → O(n × n!)
• 无法优化时间复杂度，因为必须输出所有排列
• 但可优化常数因子（如预分配空间、避免装箱）

Q3: 如果数组很大（如 n=20），还能用回溯吗？

答：不能。

• 20! ≈ 2.4 × 10^18，远超计算能力
• 此时应：
  • 仅生成第 k 个排列（数学方法）
  • 使用迭代器模式按需生成
  • 或问题本身有特殊约束可剪枝

Q4: 如何生成字典序的全排列？

答：两种方法：

1. 回溯 + 排序：先对nums排序，使用方法一（按索引顺序选）
2. 非递归算法：基于“下一个排列”逻辑（如 STLnext_permutation）

// 方法：先排序，再回溯Arrays.sort(nums);// 然后使用方法一（boolean[] used）

Q5: 回溯中的“状态恢复”为什么重要？

答：因为回溯是共享状态的递归。

• 若不恢复，后续分支会基于错误的状态计算
• 例如：第一次交换后未还原，第二次循环的output已被修改
• 导致结果重复、遗漏或错误

十一、这道算法题在实际开发中的应用

11.1 密码学：暴力破解（理论）

• 枚举所有可能的密码组合（如 PIN 码）
• 虽不实用（因现代密码强度高），但原理相同

11.2 游戏开发：解谜游戏

• 如“数独”、“华容道”的解法生成
• 枚举所有可能的移动序列

11.3 测试用例生成

• 自动生成所有参数排列，用于边界测试
• 例如：测试 API 在不同参数顺序下的行为

11.4 调度问题

• 任务调度：枚举所有任务执行顺序，寻找最优解
• （实际中因规模大，需启发式算法）

11.5 生物信息学

• DNA 序列的排列分析
• 蛋白质折叠的构型枚举

💡 虽然实际中很少直接生成全排列（因 n! 增长太快），但回溯思想广泛应用于各种搜索问题。

十二、相关题目推荐

学习路径建议：

1. 掌握本题（无重复全排列）
2. → 47（去重技巧）
3. → 78/77（子集/组合）
4. → 39/40（可重复选择）
5. → 51（复杂约束）

十三、总结与延伸

13.1 核心收获

• 回溯 = 递归 + 选择 + 撤销
• 全排列问题的标准解法是回溯
• 原地交换法空间更优，体现状态管理精髓
• 时间复杂度 O(n × n!) 是理论下限

13.2 延伸思考

如何生成第 k 个排列（LeetCode 60）？

• 利用阶乘数系（Factorial Number System）
• 无需生成所有排列，直接定位
• 时间复杂度 O(n²)，空间 O(n)

迭代式全排列生成？

• 基于邻位对换法（Johnson-Trotter）
• 每次只交换相邻元素，生成下一个排列
• 适用于需要逐个生成的场景

并行回溯？

• 对第一层分支并行（如 n 个起始元素）
• 但 n 较小时 overhead 大，不实用

13.3 学习建议

1. 动手实现：手写回溯模板（选择/递归/撤销）
2. 理解状态：明确“路径”、“选择列表”、“结束条件”
3. 区分问题类型：排列（有序） vs 组合（无序）
4. 掌握去重技巧：排序 + 跳过重复
5. 刷相关题：巩固回溯在不同场景的应用

结语：全排列虽是一道“简单”的回溯题，却蕴含了算法设计的核心思想——系统化搜索 + 状态管理。掌握它，不仅是为了解决这一道题，更是为了建立起解决更复杂组合问题的能力。希望本文能助你透彻理解回溯算法，在面试与实战中游刃有余！