本文详解 java 中使用回溯法生成整数数组所有全排列的正确实现，指出原代码因缺失「状态回退」导致仅输出一个排列，并提供可运行的修复版本及关键原理说明。
本文详解 java 中使用回溯法生成整数数组所有全排列的正确实现，指出原代码因缺失「状态回退」导致仅输出一个排列，并提供可运行的修复版本及关键原理说明。
在回溯算法中，“做选择 → 递归探索 → 撤销选择” 是核心三步模式。原代码的根本问题在于：它在每次递归前修改了 nums 和 permute 的状态（如 nums.remove(i) 和 permute.add(currInt)），但未在递归返回后恢复它们——即缺少「回溯（backtrack）」操作。这导致后续循环迭代时 nums 已被破坏（长度变短、元素错位），permute 持续累积而无法重用，最终只有第一条路径能走到底，结果仅剩 [1, 2, 3]。
以下是修正后的完整可运行代码：
import java.util.*;
public class ArrayPermutations {
public static void helper(List<List<Integer>> result, List<Integer> current, List<Integer> nums) {
// 终止条件：nums 为空，当前排列完成
if (nums.isEmpty()) {
result.add(new ArrayList<>(current));
return;
}
// 尝试每个可用数字作为当前位置的选择
for (int i = 0; i < nums.size(); i++) {
int currInt = nums.get(i);
// 【做选择】
nums.remove(i); // 从候选集中移除该数
current.add(currInt); // 加入当前排列
// 【递归探索】
helper(result, current, nums);
// 【撤销选择 / 回溯】⚠️ 关键修复点
current.remove(current.size() - 1); // 恢复 current 状态
nums.add(i, currInt); // 将该数插回原位置，恢复 nums 状态
}
}
public static List<List<Integer>> permute(int[] num) {
List<Integer> nums = new ArrayList<>();
for (int value : num) {
nums.add(value);
}
List<List<Integer>> result = new ArrayList<>();
List<Integer> current = new ArrayList<>();
helper(result, current, nums);
return result;
}
public static void main(String[] args) {
int[] num = {1, 2, 3};
List<List<Integer>> result = permute(num);
System.out.println(result);
// 输出: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
}
}关键要点说明：
Alibabacloud Sdk Client Initialization For Java
下载
在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。
- ✅
current.remove(current.size() - 1)：确保每次递归返回后，current回到进入递归前的状态，避免残留元素干扰下一轮选择； - ✅
nums.add(i, currInt)：将取出的元素精准插回原索引位置（而非简单add(currInt)），保证nums的顺序与大小在每轮循环开始时始终一致； - ❌ 原代码中
helper(..., permute.add(currInt), ...)是严重错误：List.add()返回boolean，而非List，且该调用会永久修改permute，同时done参数完全未被使用，属于冗余设计； - ? 回溯的本质不是“不修改”，而是“修改后必须可逆”——所有共享状态（
current、nums）都需在递归前后严格对称地变更与恢复。
掌握这一模式后，你可轻松迁移至其他回溯问题（如组合、子集、N 皇后等）。记住：没有回溯的递归，只是单向深搜；有了回溯，才真正拥有了“试探—失败—重来”的智能搜索能力。
立即学习“Java免费学习笔记（深入）”；
