经典回溯算法应用案例（2） - 全排列问题

1. 问题描述与目标

全排列问题是一个经典的回溯算法应用问题。问题要求给定一个没有重复元素的整数数组，返回该数组的所有可能排列。比如，对于数组 [1, 2, 3]，全排列的结果应为：

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

全排列问题的核心是求出数组中所有元素的不同排列方式，因此，解决该问题时我们需要保证不遗漏任何一个排列，同时避免重复排列的产生。

2. 回溯算法在全排列中的应用

回溯算法在全排列问题中的应用主要是通过递归和交换元素来生成所有的排列。具体思路是：从数组的第一个位置开始，尝试将当前位置的元素与后续的元素交换，每次交换后递归处理剩下的元素。每一次递归到数组的最后位置时，我们就得到了一个完整的排列。

通过回溯算法，我们可以在一个候选解空间中一步步地试探，并在发现某个选择无法继续下去时“回退”到上一步，选择一个新的路径继续探索。回溯算法的主要优势是能够全面穷举所有的可能性，并且在解空间中进行“剪枝”以提高效率。

3. 实现步骤与代码解析

下面是基于回溯算法实现全排列问题的 Java 代码：

import java.util.*;

public class Permutation {
    
    // 用于保存所有的排列
    private List<List<Integer>> result = new ArrayList<>();
    
    public List<List<Integer>> permute(int[] nums) {
        // 如果数组为空，返回空结果
        if (nums == null || nums.length == 0) {
            return result;
        }
        
        // 创建一个列表保存当前的排列
        List<Integer> currentPermutation = new ArrayList<>();
        
        // 创建一个标记数组来避免重复使用相同的元素
        boolean[] used = new boolean[nums.length];
        
        // 调用回溯函数
        backtrack(nums, currentPermutation, used);
        
        return result;
    }

    private void backtrack(int[] nums, List<Integer> currentPermutation, boolean[] used) {
        // 如果当前排列的大小等于数组长度，说明我们已经生成了一个完整的排列
        if (currentPermutation.size() == nums.length) {
            result.add(new ArrayList<>(currentPermutation)); // 将当前排列加入结果中
            return;
        }

        // 遍历数组中的每个元素，尝试将其加入排列
        for (int i = 0; i < nums.length; i++) {
            // 如果该元素已经被使用过，就跳过
            if (used[i]) {
                continue;
            }
            
            // 选择当前元素并标记为已使用
            used[i] = true;
            currentPermutation.add(nums[i]);
            
            // 递归处理剩下的元素
            backtrack(nums, currentPermutation, used);
            
            // 回溯：撤销选择，恢复状态
            currentPermutation.remove(currentPermutation.size() - 1);
            used[i] = false;
        }
    }

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

3.1 代码解析：

递归回溯函数：backtrack(nums, currentPermutation, used) 负责生成全排列。在这个函数中，我们通过循环遍历数组中的每个元素，检查该元素是否已被使用。如果未使用，则将其加入当前排列 currentPermutation，并递归调用 backtrack 来处理下一个元素。递归结束后，撤销当前选择，恢复状态，继续尝试其他的可能性。
递归终止条件：当 currentPermutation 的大小等于 nums 数组的长度时，说明当前排列已完成。我们将其复制并添加到 result 中。
标记数组 used：为了避免重复选择同一个元素，使用一个布尔数组 used 来标记哪些元素已经被选中。这样可以确保在生成排列的过程中不会重复使用元素。
回溯：回溯的核心在于在每次选择元素后都递归，递归完成后撤销当前选择并回到上一步，继续尝试其他的选择。