如何正确实现数组全排列的回溯算法（Java 教程）-java教程-PHP中文网

如何正确实现数组全排列的回溯算法（Java 教程）

本文详解 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>> result, List<integer> current, List<integer> nums) {
        // 终止条件：nums 为空，当前排列完成
        if (nums.isEmpty()) {
            result.add(new ArrayList(current));
            return;
        }

        // 尝试每个可用数字作为当前位置的选择
        for (int i = 0; i > permute(int[] num) {
        List<integer> nums = new ArrayList();
        for (int value : num) {
            nums.add(value);
        }
        List<list>> 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>> 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]]
    }
}</list></integer></list></integer></integer></integer></list>

关键要点说明：

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）都需在递归前后严格对称地变更与恢复。