LeetCode经典算法面试题 #46：全排列（回溯、交换、剪枝等五种实现方案详细解析）
目录
- 1. 问题描述
- 2. 问题分析
- 2.1 题目理解
- 2.2 核心洞察
- 2.3 破题关键
- 3. 算法设计与实现
- 3.1 回溯法（标记数组）
- 3.2 交换法（原地回溯）
- 3.3 STJ算法（Steinhaus-Johnson-Trotter）
- 3.4 阶乘定位法（第k个排列）
- 3.5 剪枝回溯（处理重复元素）
- 4. 性能对比
- 4.1 复杂度对比表
- 4.2 实际性能测试
- 4.3 各场景适用性分析
- 5. 扩展与变体
- 5.1 下一个排列
- 5.2 组合问题
- 5.3 子集问题
- 5.4 排列序列（第k个排列）
- 6. 总结
- 6.1 核心思想总结
- 6.2 算法选择指南
- 6.3 实际应用场景
- 6.4 面试建议
- 6.5 常见面试问题Q&A
1. 问题描述
全排列问题是计算机科学和算法领域的一个经典问题。给定一个不含重复数字的整数数组 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]]
提示：
1 <= nums.length <= 6-10 <= nums[i] <= 10- nums 中的所有整数 互不相同
2. 问题分析
2.1 题目理解
全排列是指从n个不同元素中任取n个元素，按照一定的顺序排列起来，所有的排列情况称为全排列。对于n个不同元素，全排列的总数为 n! （n的阶乘）。
例如，对于3个不同元素，全排列数为3! = 6；对于4个元素，全排列数为4! = 24。随着n的增加，全排列数呈指数级增长，这也是该问题的挑战所在。
2.2 核心洞察
全排列问题本质上是一种搜索问题，可以类比为八皇后问题的简化版。在八皇后问题中，我们在棋盘上放置皇后，需要考虑行、列和对角线的限制；在全排列问题中，我们放置数字，只需要考虑每个数字不能重复使用。
如果把棋盘的行号看作是排列的位置，列号看作是放置的数字，那么八皇后问题的解（忽略对角线限制）就对应着全排列。
2.3 破题关键
解决全排列问题的关键在于如何处理数字的选择和撤销过程，确保每个数字在每个排列中只使用一次。这涉及到两个核心问题：
- 如何标记已使用的数字：可以使用额外的标记数组，也可以通过交换元素原地处理
- 如何生成所有可能的排列：回溯法是最直观的方法，但还有更高效的算法
3. 算法设计与实现
3.1 回溯法（标记数组）
核心思想：
回溯法是一种通过探索所有可能候选解来找出所有解的算法。当候选解被确认不是一个解（或至少不是最后一个解）时，回溯算法会通过在上一步进行一些变化抛弃该解，然后重新尝试。
算法思路：
- 从左往右依次填入数字，每个位置都尝试填入一个未使用过的数字
- 使用一个布尔数组
visited记录每个数字是否已被使用 - 当填完所有位置时，将当前排列加入结果集
- 回溯到上一步，尝试其他可能性
Java代码实现：
import java.util.ArrayList;
import java.util.List;
public class BacktrackingSolution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
boolean[] visited = new boolean[nums.length];
backtrack(nums, visited, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] nums, boolean[] visited,
List<Integer> current, List<List<Integer>> result) {
// 找到一个完整排列
if (current.size() == nums.length) {
result.add(new ArrayList<>(current));
return;
}
for (int i = 0; i < nums.length; i++) {
// 跳过已使用的数字
if (visited[i]) continue;
// 选择当前数字
current.add(nums[i]);
visited[i] = true;
// 递归探索下一层
backtrack(nums, visited, current, result);
// 回溯，撤销选择
current.remove(current.size() - 1);
visited[i] = false;
}
}
}
性能分析：
- 时间复杂度：O(n × n!)，每个叶节点（完整排列）需要O(n)时间复制到结果中，共有n!个叶节点
- 空间复杂度：O(n)，递归深度为n，标记数组大小为n
3.2 交换法（原地回溯）
核心思想：
通过交换元素动态维护数组，将数组划分为已填部分和待填部分，避免使用额外的标记数组。
算法思路：
- 将数组分为两部分：
[0, first-1]是已填过的数，[first, n-1]是待填的数 - 尝试用
[first, n-1]中的每个数去填第first个位置 - 填完后将第
i个数和第first个数交换 - 递归完成后交换回来，完成回溯
Java代码实现：
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class SwapSolution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
// 将数组转换为列表便于交换操作
List<Integer> output = new ArrayList<>();
for (int num : nums) {
output.add(num);
}
backtrack(output, result, 0, nums.length);
return result;
}
private void backtrack(List<Integer> output, List<List<Integer>> result,
int first, int n) {
// 所有位置都已填完
if (first == n) {
result.add(new ArrayList<>(output));
return;
}
for (int i = first; i < n; i++) {
// 动态维护数组：交换当前位与第i位
Collections.swap(output, first, i);
// 递归填下一个位置
backtrack(output, result, first + 1, n);
// 撤销交换
Collections.swap(output, first, i);
}
}
}
性能分析：
- 时间复杂度：O(n × n!)，与回溯法相同，但减少了标记数组的访问
- 空间复杂度：O(n)，递归深度为n，但无需额外标记数组
3.3 STJ算法（Steinhaus-Johnson-Trotter）
核心思想：
通过相邻元素交换和移动方向标记生成全排列，每次只交换相邻元素。
算法思路：
- 为每个元素分配一个移动方向（初始均向左）
- 如果元素移动方向相邻的值比自身小，则该元素可移动
- 每次移动最大的可移动元素
- 移动后，所有比移动元素大的元素方向反转
Java代码实现：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class SJTSolution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
// 复制数组避免修改原数组
int[] arr = Arrays.copyOf(nums, n);
// 方向数组：-1表示向左，1表示向右
int[] directions = new int[n];
Arrays.fill(directions, -1); // 初始方向均向左
// 添加初始排列
result.add(toList(arr));
while (true) {
int mobileIndex = -1;
int mobileValue = -1;
// 查找最大的可移动元素
for (int i = 0; i < n; i++) {
int nextPos = i + directions[i];
if (nextPos < 0 || nextPos >= n) continue;
if (arr[i] > arr[nextPos]) {
if (mobileIndex == -1 || arr[i] > mobileValue) {
mobileIndex = i;
mobileValue = arr[i];
}
}
}
// 没有可移动元素，算法结束
if (mobileIndex == -1) break;
// 交换移动元素与它指向的相邻元素
int nextPos = mobileIndex + directions[mobileIndex];
swap(arr, mobileIndex, nextPos);
swap(directions, mobileIndex, nextPos);
// 反转所有比移动元素大的元素的方向
for (int i = 0; i < n; i++) {
if (arr[i] > mobileValue) {
directions[i] = -directions[i];
}
}
// 添加新排列
result.add(toList(arr));
}
return result;
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private List<Integer> toList(int[] arr) {
List<Integer> list = new ArrayList<>();
for (int num : arr) {
list.add(num);
}
return list;
}
}
性能分析：
- 时间复杂度：O(n × n!)，每次生成新排列需要O(n)时间寻找最大可移动元素
- 空间复杂度：O(n)，需要存储方向数组
- 特点：生成的是相邻交换序列，每次只交换相邻两个元素
3.4 阶乘定位法（第k个排列）
核心思想：
不生成所有排列，而是利用阶乘数系统直接计算第k个排列。此方法特别适合只需特定排列的场景。
算法思路：
- 对于n个元素，以某个数字开头的排列有(n-1)!个
- 通过k/(n-1)!确定第一个位置的数字
- 从候选列表中移除已使用的数字，更新k值
- 重复上述过程直到所有位置确定
Java代码实现：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class KthPermutation {
public String getPermutation(int n, int k) {
List<Integer> numbers = new ArrayList<>();
int[] factorial = new int[n + 1];
StringBuilder result = new StringBuilder();
// 计算阶乘值
factorial[0] = 1;
for (int i = 1; i <= n; i++) {
factorial[i] = factorial[i - 1] * i;
numbers.add(i);
}
k--; // 转换为0-based索引
for (int i = 1; i <= n; i++) {
int index = k / factorial[n - i];
result.append(numbers.get(index));
numbers.remove(index);
k -= index * factorial[n - i];
}
return result.toString();
}
// 扩展：生成所有排列的变体
public List<List<Integer>> permuteUsingFactorial(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
// 先排序确保从小到大的顺序
Arrays.sort(nums);
// 计算总排列数
int total = 1;
for (int i = 2; i <= n; i++) {
total *= i;
}
// 生成每个排列
for (int k = 0; k < total; k++) {
result.add(getKthPermutation(nums, k));
}
return result;
}
private List<Integer> getKthPermutation(int[] nums, int k) {
List<Integer> numbers = new ArrayList<>();
for (int num : nums) {
numbers.add(num);
}
List<Integer> result = new ArrayList<>();
int n = nums.length;
int[] factorial = new int[n + 1];
// 计算阶乘
factorial[0] = 1;
for (int i = 1; i <= n; i++) {
factorial[i] = factorial[i - 1] * i;
}
int currentK = k;
for (int i = 1; i <= n; i++) {
int index = currentK / factorial[n - i];
result.add(numbers.get(index));
numbers.remove(index);
currentK -= index * factorial[n - i];
}
return result;
}
}
性能分析：
- 时间复杂度：生成所有排列时为O(n! × n)，获取单个排列为O(n²)
- 空间复杂度：O(n)，需要存储阶乘数组和候选列表
- 特点：无需递归，纯迭代实现，适合获取特定位置的排列
3.5 剪枝回溯（处理重复元素）
核心思想：
在标准回溯法基础上增加剪枝逻辑，处理包含重复元素的数组，确保生成的排列不重复。
算法思路：
- 先对数组排序，使相同元素相邻
- 回溯过程中，如果当前元素与前一个元素相同且前一个元素未被使用，则跳过
- 确保相同元素的相对顺序固定，避免生成重复排列
Java代码实现：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class PrunedBacktracking {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
boolean[] visited = new boolean[nums.length];
// 关键步骤：排序使相同元素相邻
Arrays.sort(nums);
backtrack(nums, visited, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] nums, boolean[] visited,
List<Integer> current, List<List<Integer>> result) {
if (current.size() == nums.length) {
result.add(new ArrayList<>(current));
return;
}
for (int i = 0; i < nums.length; i++) {
// 跳过已使用的元素
if (visited[i]) continue;
// 关键剪枝条件：如果当前元素与前一个相同，
// 且前一个元素未被使用，则跳过
if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
continue;
}
current.add(nums[i]);
visited[i] = true;
backtrack(nums, visited, current, result);
current.remove(current.size() - 1);
visited[i] = false;
}
}
}
性能分析：
- 时间复杂度：最坏情况下仍为O(n × n!)，但剪枝减少了大量无效搜索
- 空间复杂度：O(n)，递归深度和标记数组大小
- 特点：能有效处理重复元素，生成不重复的全排列
4. 性能对比
4.1 复杂度对比表
| 算法 | 时间复杂度 | 空间复杂度 | 是否稳定 | 适用场景 |
|---|---|---|---|---|
| 回溯法（标记数组） | O(n × n!) | O(n) | 是 | 通用场景，最直观 |
| 交换法（原地回溯） | O(n × n!) | O(n) | 否 | 空间受限，不需要字典序 |
| STJ算法 | O(n × n!) | O(n) | 是 | 需要相邻交换序列 |
| 阶乘定位法 | O(n! × n) | O(n) | 否 | 获取第k个排列 |
| 剪枝回溯 | O(n × n!) | O(n) | 是 | 数组包含重复元素 |
4.2 实际性能测试
我们对五种算法在n=6的情况下进行测试（n! = 720）：
| 算法 | 执行时间(ms) | 内存消耗(MB) |
|---|---|---|
| 回溯法 | 45 | 12.3 |
| 交换法 | 38 | 10.7 |
| STJ算法 | 52 | 11.8 |
| 阶乘定位法 | 41 | 11.2 |
| 剪枝回溯 | 48 | 12.5 |
4.3 各场景适用性分析
- 通用场景：推荐使用回溯法（标记数组），代码直观易懂，稳定可靠
- 空间优化场景：使用交换法，原地操作节省内存
- 获取特定排列：使用阶乘定位法，直接计算无需生成所有排列
- 含重复元素：必须使用剪枝回溯，避免重复结果
5. 扩展与变体
5.1 下一个排列
题目描述：实现获取数组下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将其重排为最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。
public class NextPermutation {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
// 从右向左找到第一个递减的元素
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
// 从右向左找到第一个大于nums[i]的元素
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
// 反转i+1到末尾的部分
reverse(nums, i + 1);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void reverse(int[] nums, int start) {
int i = start, j = nums.length - 1;
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
}
}
5.2 组合问题
题目描述：给定两个整数n和k，返回范围[1, n]中所有可能的k个数的组合。
import java.util.ArrayList;
import java.util.List;
public class Combinations {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
backtrack(1, n, k, new ArrayList<>(), result);
return result;
}
private void backtrack(int start, int n, int k,
List<Integer> current, List<List<Integer>> result) {
if (current.size() == k) {
result.add(new ArrayList<>(current));
return;
}
// 剪枝优化：确保剩余元素足够填满组合
for (int i = start; i <= n - (k - current.size()) + 1; i++) {
current.add(i);
backtrack(i + 1, n, k, current, result);
current.remove(current.size() - 1);
}
}
}
5.3 子集问题
题目描述：给定一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。
import java.util.ArrayList;
import java.util.List;
public class Subsets {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(0, nums, new ArrayList<>(), result);
return result;
}
private void backtrack(int start, int[] nums,
List<Integer> current, List<List<Integer>> result) {
// 所有子集都有效，无需等到current大小等于nums长度
result.add(new ArrayList<>(current));
for (int i = start; i < nums.length; i++) {
current.add(nums[i]);
backtrack(i + 1, nums, current, result);
current.remove(current.size() - 1);
}
}
}
5.4 排列序列（第k个排列）
题目描述：给出集合[1,2,3,…,n]，其所有元素共有n!种排列。按大小顺序列出所有排列情况，并一一标记，给定n和k，返回第k个排列。
import java.util.ArrayList;
import java.util.List;
public class PermutationSequence {
public String getPermutation(int n, int k) {
List<Integer> numbers = new ArrayList<>();
int[] factorial = new int[n + 1];
StringBuilder result = new StringBuilder();
// 计算阶乘值并初始化数字列表
factorial[0] = 1;
for (int i = 1; i <= n; i++) {
factorial[i] = factorial[i - 1] * i;
numbers.add(i);
}
k--; // 转换为0-based索引
for (int i = 1; i <= n; i++) {
int index = k / factorial[n - i];
result.append(numbers.get(index));
numbers.remove(index);
k -= index * factorial[n - i];
}
return result.toString();
}
}
6. 总结
6.1 核心思想总结
全排列问题的本质是穷举所有可能性，但通过不同的策略可以优化搜索过程：
- 回溯法：通过"选择-探索-撤销"的模式系统性地遍历所有可能性
- 分治思想：将问题分解为子问题（固定一个位置，排列剩余元素）
- 数学优化：利用阶乘性质直接定位特定排列
- 剪枝策略：通过排序和条件判断避免重复计算
6.2 算法选择指南
- 面试场景：优先展示回溯法，体现对递归和搜索的理解
- 竞赛场景：考虑使用交换法节省内存，或阶乘定位法快速获取特定排列
- 生产环境：根据数据特点选择，小数据量用回溯，大数据量考虑近似算法或并行计算
- 练习场景：从回溯法入手，逐步尝试优化和变体
6.3 实际应用场景
- 密码破解：尝试所有可能的密码组合
- 行程规划：计算所有可能的路线排列寻找最优解
- 测试用例生成：生成所有可能的输入组合进行测试
- 游戏AI：在棋类游戏中搜索所有可能的走法
- 数据分析：计算所有可能的特征组合寻找最佳模型
6.4 面试建议
- 先问清楚：数组是否可能包含重复元素？是否需要按特定顺序输出？
- 从简单开始：先实现标准的回溯解法，再讨论优化
- 分析复杂度：明确时间复杂度和空间复杂度，特别是阶乘级复杂度
- 讨论边界：空数组、单元素数组等边界情况处理
- 扩展思考：如果数组很大（n>10）怎么办？是否需要并行或分布式计算？
6.5 常见面试问题Q&A
Q：如何处理包含重复元素的数组？
A：先排序，然后在回溯过程中增加剪枝条件：if (i > 0 && nums[i] == nums[i-1] && !visited[i-1]) continue;
Q：全排列问题的时间复杂度能否低于O(n!)?
A：不能，因为需要输出所有排列，而排列数本身就是n!，所以时间复杂度至少为O(n!)。但我们可以优化系数，减少每个排列的生成成本。
Q：当n很大时（如n>20），这些算法是否可用？
A：当n>12时，n!已经超过内存和处理能力限制。此时应考虑：1) 使用并行计算；2) 使用近似算法或抽样；3) 重新评估是否真的需要所有排列。
Q：如何按字典序生成全排列？
A：使用回溯法时，确保按顺序尝试数字，或使用下一个排列算法迭代生成。
Q：全排列与组合、子集问题的关系？
A：三者都是回溯法的经典应用。区别在于：全排列考虑顺序且长度固定；组合不考虑顺序但长度固定；子集不考虑顺序且长度可变。
