回溯算法12-全排列II(Java/排列数去重操作)

12.全排列II

题目描述

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

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

示例 2：

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

题目分析

本题目所描述的全排列存在重复的情况，当nums={1,1,2}时，就会出现两个[1,1,2]的情况，这是由于同一树层，两次添加了1这一相同的元素导致，所以我们需要对树层的元素进行去重操作

1.首先我们将nums数组中的元素进行排序，这样有利于我们将相同的元素同一在一起
2.对于树层上的去重，当我们发下有两个相邻的重复元素时，我们可以进行去重，为了防止类似[1,1]这样的元素被去除，我们可以观察发现
当nums[i] == nums[i - 1] && used[i - 1] == 0时去重可以避免这种情况
解释：在这个条件语句中，首先判断 i 是否大于 0，这是为了避免数组下标越界。然后判断 nums[i] == nums[i - 1]，这个条件用来检查当前数字是否与前一个数字相同，也就是判断是否存在重复的数字。最后一个条件 used[i - 1] == 0 则是用来确保前一个相同的数字已经被使用过，如果前一个相同的数字还未被使用，那么当前的排列会和之前的排列重复，因此需要跳过这种情况。

完整代码思路

1.首先，定义了两个全局变量 path 和 result，分别用于存储当前的路径和最终的结果。path 是一个链表，用于暂时存储当前的排列，result 是一个列表，用于存储所有的排列组合。

2.然后，定义了一个 permute 方法，接受一个整数数组 nums 作为参数，并返回所有排列的列表。在该方法中，首先初始化了一个长度与 nums 相同的数组 used，用于标记每个数字是否被使用过。然后对 nums 数组进行排序，以确保重复的数字都相邻。接着调用 backtrack 方法开始搜索排列。

3.在 backtrack 方法中，首先判断当前的排列长度是否等于 nums 的长度，如果是，则将当前排列加入到 result 中，并返回。接着，使用一个循环遍历 nums 数组中的每个元素，对于每个元素，首先判断是否存在重复的情况，如果存在重复且之前的重复数字未被使用，则跳过当前循环。然后再判断当前元素是否已经被使用过，如果是，则跳过当前循环。如果都不满足，则将当前元素标记为已使用，添加到 path 中，然后递归调用 backtrack 方法继续搜索下一层排列。当递归结束后，将当前元素从 path 中移除，并将其标记为未使用，以便尝试其他可能的排列组合。

4.通过这样的回溯过程，最终可以得到所有的排列组合。

Java代码实现

LinkedList<Integer> path = new LinkedList<>(); // 用于存储当前路径的链表
List<List<Integer>> result = new ArrayList<>(); // 用于存储最终结果的列表

public List<List<Integer>> permute(int[] nums) {
    int[] used = new int[nums.length]; // 用于标记数字是否被使用过的数组
    Arrays.sort(nums); // 对输入的数组进行排序，确保相同的数字连续出现

    backtrack(nums, used, 0); // 调用回溯函数进行全排列

    return result; // 返回最终结果
}

private void backtrack(int[] nums, int[] used, int startIndex) {
    if (path.size() == nums.length) { // 如果当前路径长度等于数组长度，说明已经找到一个全排列
        result.add(new ArrayList<>(path)); // 将当前路径添加到结果集中
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0) continue; 
        // 当前数字与前一个数字相等，并且前一个数字未被使用过，则跳过当前循环，避免重复排列

        if (used[i] == 1) continue; // 如果当前数字已经被使用过，则跳过当前循环

        used[i] = 1; // 标记当前数字为已使用
        path.add(nums[i]); // 将当前数字添加到路径中
        backtrack(nums, used, startIndex + 1); // 递归进入下一层，继续寻找全排列
        path.removeLast(); // 回溯，将最后一个数字从路径中移除
        used[i] = 0; // 标记当前数字为未使用，以便后续使用
    }
}