Java回溯算法解析LeetCode 46：数组全排列的两种实现

问题描述

来源：LeetCode第46题

难度：中等

给定一个不含重复数字的数组 nums，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例 1：

输入：nums = [1,2,3]
输出：1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1

示例 2：

输入：nums = [0,1]
输出：0,1],[1,0

示例 3：

输入：nums = [1]
输出：1

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums中的所有整数互不相同

回溯算法解决

全排列是回溯算法的经典应用场景。我们可以将求解过程抽象为一棵n叉树的深度优先遍历（DFS），其中n是数组的长度。第一层有n个选择（所有数字），第二层有n-1个选择（排除已选的数字），依此类推，直到叶子节点形成一个完整的排列。

核心思路是：做出选择、递归探索、撤销选择（回溯）。如果不撤销选择，临时列表会包含所有遍历过的数字，导致结果错误。

让我们先看一个初步但不完整的实现，以便理解问题所在：

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    backtrack(list, new ArrayList<>(), nums);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums) {
    // 终止条件：如果临时列表长度等于数组长度，说明找到了一个完整排列
    if (tempList.size() == nums.length) {
        // 注意：必须创建一个新列表，因为tempList是引用
        list.add(new ArrayList<>(tempList));
        return;
    }
    // 遍历所有可能的选择
    for (int i = 0; i < nums.length; i++) {
        // 跳过已经存在于临时列表中的数字（避免重复）
        if (tempList.contains(nums[i]))
            continue;
        // 做出选择：将当前数字加入路径
        tempList.add(nums[i]);
        // 递归：基于当前选择继续探索
        backtrack(list, tempList, nums);
        // 问题所在：缺少了“撤销选择”的步骤！
    }
}

如果用数组[1,2,3]测试这段代码，输出结果只会是[[1, 2, 3]]，而不是全部6种排列。这是因为在递归返回后，tempList没有移除最后添加的元素，导致它包含了所有递归路径上的数字，无法形成新的分支。

正确的做法是在递归调用后立即撤销刚才的选择：

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    backtrack(list, new ArrayList<>(), nums);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums) {
    if (tempList.size() == nums.length) {
        list.add(new ArrayList<>(tempList));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (tempList.contains(nums[i]))
            continue;
        // 做出选择
        tempList.add(nums[i]);
        // 递归探索
        backtrack(list, tempList, nums);
        // 撤销选择（回溯）：移除最后加入的元素
        tempList.remove(tempList.size() - 1);
    }
}

现在，再次测试数组[1,2,3]，将得到完整的输出：

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

交换法回溯

除了使用临时列表记录路径，另一种巧妙的回溯算法思路是通过交换数组元素来直接生成排列。

思路如下：从第一个位置（index = 0）开始，将这个位置的数字与它之后（包括自身）的每一个数字交换。每次交换后，固定第一个位置的数字，然后对从第二个位置开始的子数组进行同样的递归操作。递归到底层生成一个排列后，需要再次交换回来（回溯），以恢复数组状态，进行下一次交换。

这个过程可以用以下树状图来直观理解：

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, res);
    return res;
}

public void backtrack(int[] nums, int index, List<List<Integer>> res) {
    // 终止条件：到达最后一个位置，无法再交换，当前数组即为一个排列
    if (index == nums.length - 1) {
        List<Integer> tempList = new ArrayList<>();
        for (int num : nums)
            tempList.add(num);
        res.add(tempList);
        return;
    }
    // 将index位置的元素与后面所有位置的元素（包括自己）依次交换
    for (int i = index; i < nums.length; i++) {
        swap(nums, index, i);      // 做出选择：交换
        backtrack(nums, index + 1, res); // 递归处理下一个位置
        swap(nums, index, i);      // 撤销选择：交换回来（回溯）
    }
}

// 交换两个数字的值
private void swap(int[] nums, int i, int j) {
    if (i != j) {
        nums[i] ^= nums[j];
        nums[j] ^= nums[i];
        nums[i] ^= nums[j];
    }
}

递归分治法

我们还可以从分治的角度来思考全排列问题。一个数组 [1,2,3] 的全排列，可以看作是在其子数组 [2,3] 的所有排列中，将数字 1 插入到每一个可能的位置。

具体来说：

1. 先求出子数组（nums[index+1:]）的全排列结果。
2. 将当前数字（nums[index]）插入到每一个子排列的所有可能位置（头部、中间、尾部）。

// 递归解决
public List<List<Integer>> permute(int[] nums) {
    return helper(nums, 0);
}

/**
 * @param nums  原始数组
 * @param index 当前处理的起始下标
 * @return 从index开始的子数组的全排列
 */
private List<List<Integer>> helper(int[] nums, int index) {
    List<List<Integer>> res = new ArrayList<>();
    // 递归终止条件：只剩一个元素，其全排列就是自身
    if (index == nums.length - 1) {
        List<Integer> temp = new ArrayList<>();
        temp.add(nums[index]);
        res.add(temp);
        return res;
    }
    // 递归计算后面子数组的全排列
    List<List<Integer>> subList = helper(nums, index + 1);
    // 子排列的长度
    int count = subList.get(0).size();
    // 遍历每一个子排列
    for (int i = 0, size = subList.size(); i < size; i++) {
        // 将当前数字nums[index]插入到子排列的每一个可能位置（0 到 count）
        for (int j = 0; j <= count; j++) {
            // 创建子排列的副本，避免修改原数据
            List<Integer> temp = new ArrayList<>(subList.get(i));
            temp.add(j, nums[index]); // 在位置j插入
            res.add(temp);
        }
    }
    return res;
}

总结

本文详细讲解了解决LeetCode 46题“全排列”的三种方法，核心是两种回溯算法的实现（路径记录法和交换法）以及一种递归分治思想。路径记录法最直观，通过列表的增删模拟选择与回溯；交换法则直接在原数组上操作，空间效率更高。分治法提供了另一种解决问题的视角。在云栈社区的算法板块中，你可以找到更多关于Java算法实现的深入讨论和练习题。理解并掌握这些方法，对于应对算法面试和深化对递归、回溯思想的理解都大有裨益。