Java回溯实现数组全排列异常：仅输出一种排列求排查

你的代码核心问题是缺少回溯的撤销操作，同时存在冗余参数，导致递归仅遍历了一条路径就终止，无法生成所有排列。以下是具体问题分析和修复方案：

问题点分析 #

1. 未恢复剩余数字集合的状态
   循环中移除了nums中的元素，但递归返回后没有将元素放回原位置，导致后续循环时nums已经为空，无法遍历其他分支。
2. 未恢复当前排列的状态
   向permute添加元素后，递归返回后没有移除该元素，后续的排列会在已有元素基础上叠加，无法回到上一步的选择状态。
3. 冗余参数干扰
   helper方法中的done参数完全未被使用，且调用时传入permute.add(currInt)（该方法仅返回操作是否成功的布尔值），属于无效代码。

修复后的代码 #

import java.util.*;

public class Arraypermutations {
    public static void helper(List<List<Integer>> result, List<Integer> currentPerm, List<Integer> remainingNums) {
        if (remainingNums.size() == 0) {
            result.add(new ArrayList<>(currentPerm));
            return;
        }

        for (int i = 0; i < remainingNums.size(); i++) {
            int currInt = remainingNums.get(i);
            // 做出选择：移除当前数字，加入当前排列
            remainingNums.remove(i);
            currentPerm.add(currInt);
            
            // 递归进入下一层
            helper(result, currentPerm, remainingNums);
            
            // 撤销选择：回溯，恢复原始状态
            currentPerm.remove(currentPerm.size() - 1);
            remainingNums.add(i, currInt);
        }
    }

    public static List<List<Integer>> permute(int[] num) {
        List<Integer> nums = new ArrayList<>();
        for (int i : num) {
            nums.add(i);
        }

        List<List<Integer>> result = new ArrayList<>();
        List<Integer> currentPerm = new ArrayList<>();
        helper(result, currentPerm, nums);
        return result;
    }

    public static void main(String[] args) {
        int num[] = {1,2,3};   
        List<List<Integer>> result = permute(num);
        System.out.println(result);
    }
}

修复说明 #

• 添加回溯撤销步骤：递归返回后，将当前元素从currentPerm中移除，并放回remainingNums的原索引位置，确保每次循环都基于完整的剩余数字集合进行选择。
• 移除冗余参数：删除无用的done参数，简化方法逻辑。
• 优化变量命名：将Array改为result、permute改为currentPerm、nums改为remainingNums，提升代码可读性。

运行修复后的代码，即可得到预期的全排列输出：[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

内容的提问来源于stack exchange，提问作者retam biswas