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 回溯法（标记数组）

核心思想：

回溯法是一种通过探索所有可能候选解来找出所有解的算法。当候选解被确认不是一个解（或至少不是最后一个解）时，回溯算法会通过在上一步进行一些变化抛弃该解，然后重新尝试。

算法思路：

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 交换法（原地回溯）

核心思想：

通过交换元素动态维护数组，将数组划分为已填部分和待填部分，避免使用额外的标记数组。

算法思路：

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个排列。此方法特别适合只需特定排列的场景。

算法思路：

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 复杂度对比表

4.2 实际性能测试

我们对五种算法在n=6的情况下进行测试（n! = 720）：

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 实际应用场景

6.4 面试建议

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：三者都是回溯法的经典应用。区别在于：全排列考虑顺序且长度固定；组合不考虑顺序但长度固定；子集不考虑顺序且长度可变。