本文详解 java 中使用回溯法生成整数数组所有全排列时的关键错误与修复方案，重点剖析状态还原（backtracking）缺失导致结果不全的根本原因，并提供可直接运行的完整正确代码。
本文详解 java 中使用回溯法生成整数数组所有全排列时的关键错误与修复方案，重点剖析状态还原（backtracking）缺失导致结果不全的根本原因，并提供可直接运行的完整正确代码。
在实现全排列的回溯算法时，一个常见却极易被忽视的陷阱是：未在递归返回后恢复当前状态。原始代码中，permute.add(currInt) 直接修改了 permute 列表，而 nums.remove(i) 也永久移除了元素——但后续递归调用结束后，程序并未将这些变更“撤销”。这导致：第一次递归路径走完 [1,2,3] 后，permute 已满、nums 已空，且无任何回退操作，后续分支无法继续探索，最终仅输出一个结果。
正确的回溯逻辑必须严格遵循“做选择 → 递归 → 撤销选择”三步范式。关键修复点如下：
- ✅ 撤销
current的添加操作：在helper(...)返回后，执行current.remove(current.size() - 1)，移除最后加入的元素，使current回到递归前状态； - ✅ 还原
nums的原始结构：使用nums.add(i, currInt)将刚删除的数字插回原索引位置（而非末尾），确保下一轮for循环中i对应的仍是原始顺序下的下一个候选元素； - ❌ 移除冗余参数：原代码中
boolean done无实际作用，permute.add(currInt)作为方法参数不仅语义混乱（add()返回boolean，非void），更破坏了调用链清晰性，应改为显式调用并单独处理。
以下是修复后的完整可运行代码：
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); // 撤销选择：回溯当前排列
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]]
}
}注意事项总结：
- 使用
nums.isEmpty()替代nums.size() == 0更符合 Java 习惯； -
current和nums均为引用传递，必须显式回溯，否则状态污染会贯穿整个递归树； - 若改用
int[]原地交换实现（避免频繁List增删），性能更优，但本解法优先保证逻辑清晰与教学完整性； - 所有
new ArrayList(...)均为深拷贝关键步骤，防止结果列表中多个引用指向同一对象。
掌握“选择-递归-撤销”的闭环，是写出健壮回溯算法的核心心法。
