本文详解 java 中使用回溯法生成整数数组所有全排列的正确实现，指出原代码因缺少「状态回退」导致仅输出一个排列，并提供修复后的完整可运行代码及关键原理说明。
本文详解 java 中使用回溯法生成整数数组所有全排列的正确实现，指出原代码因缺少「状态回退」导致仅输出一个排列，并提供修复后的完整可运行代码及关键原理说明。
在解决全排列问题时，回溯法的核心在于：递归探索每一种选择 → 作出选择（修改状态）→ 进入下一层递归 → 递归返回后撤销选择（恢复状态）。原代码的根本缺陷在于——它只做了“前进”（nums.remove(i) 和 permute.add(currInt)），却未执行关键的“回退”操作，导致 nums 和 permute 在首次递归到底后被永久破坏，后续循环无法基于原始候选集继续分支，最终仅生成 [1,2,3] 这一个结果。
修复的关键有三点：
-
移除冗余参数：
boolean done无实际用途，应删除； -
显式回溯逻辑：每次递归调用后，必须将
current中刚加入的元素移除（current.remove(current.size() - 1)），并将nums中被移走的元素插回原位置（nums.add(i, currInt)），确保下一次for循环面对的是未被污染的候选列表； -
避免副作用传递：
permute.add(currInt)返回boolean，不能直接作为helper()的参数（原代码中helper(..., permute.add(currInt), ...)是语法错误且逻辑混乱），应拆分为独立语句。
以下是修正后的完整、可运行代码：
Alibabacloud Sdk Client Initialization For Java
下载
在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。
import java.util.*;
public class ArrayPermutations {
public static void helper(List<List<Integer>> result, List<Integer> current, List<Integer> 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); // 撤销路径添加
nums.add(i, currInt); // 将数字插回原索引位置，恢复候选集
}
}
public static List<List<Integer>> permute(int[] num) {
List<Integer> nums = new ArrayList<>();
for (int val : num) nums.add(val);
List<List<Integer>> result = new ArrayList<>();
helper(result, new ArrayList<>(), 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]]
}
}注意事项与最佳实践：
立即学习“Java免费学习笔记（深入）”；
- ✅ 始终在递归调用后执行对称的「撤销操作」，这是回溯法正确性的基石；
- ✅ 使用
new ArrayList(current)而非直接result.add(current)，防止后续修改影响已保存的结果； - ✅ 推荐将辅助方法参数命名更语义化（如
result/current/nums），提升可读性； - ⚠️ 避免在递归中直接修改传入的集合而不恢复——这是初学者最常见的回溯失效原因。
掌握这一模式后，你可轻松迁移至组合、子集、N 皇后等其他经典回溯问题。
