594，回溯算法解含有重复数字的全排列 II

Original 博哥数据结构和算法 2022-05-10

问题描述

来源：LeetCode第47题

难度：中等

给定一个可包含重复数字的序列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]]

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10

回溯算法解决

这题和前面讲的593，经典回溯算法题-全排列差不多，不过这题有重复数字，但593题没有重复数字。有重复的数字肯定就会有重复的组合，所以这题需要过滤掉重复的组合。如果不过滤会有什么结果，我们以示例一为例来个图来看一下（这里为了区分第一个1和第二个1，我分别用了黑色和红色标记，在公众号中如果看不清可以点击放大）。

怎么样才能过滤掉重复的数字呢，一种方式就是找出所有的组合结果，然后在这个结果中过滤掉重复的组合。如果组合是字符串还好比较，但这里是个数组，所有数组两两比较复杂度太高，这种方式我们不考虑。

除了上面说的一种解法还有一种方式就是我们常说的剪枝，怎么剪呢？因为要过滤掉重复的，只有重复的数字才会造成重复的结果。所以第一步要做的就是对数组进行排序，排序之后相同的数字肯定是挨着的。

当遍历到当前数字的时候，如果数组中当前数字和前一个数字一样，并且前一个数字没有被使用，我们就跳过当前分支，也就是把当前分支给剪掉。如下图所示

代码如下

public List<List<Integer>> permuteUnique(int[] nums) {
    //先对数组进行排序，这样做目的是相同的值在数组中肯定是挨着的，
    //方便过滤掉重复的结果
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    //boolean数组，used[i]表示元素nums[i]是否被访问过
    boolean[] used = new boolean[nums.length];
    //执行回溯算法
    backtrack(nums, used, new ArrayList<>(), res);
    return res;
}

public void backtrack(int[] nums, boolean[] used, List<Integer> tempList, List<List<Integer>> res) {
    //如果数组中的所有元素都使用完了，类似于到了叶子节点，
    //我们直接把从根节点到当前叶子节点这条路径的元素加入
    //到集合res中
    if (tempList.size() == nums.length) {
        res.add(new ArrayList<>(tempList));
        return;
    }
    //遍历数组中的元素
    for (int i = 0; i < nums.length; i++) {
        //如果已经被使用过，则直接跳过
        if (used[i])
            continue;
        //注意，这里要剪掉重复的组合
        //如果当前元素和前一个一样，并且前一个没有被使用过，我们也跳过
        if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1])
            continue;
        //否则我们就使用当前元素，把他标记为已使用
        used[i] = true;
        //把当前元素nums[i]添加到tempList中
        tempList.add(nums[i]);
        //递归，类似于n叉树的遍历，继续往下走
        backtrack(nums, used, tempList, res);
        //递归完之后会往回走，往回走的时候要撤销选择
        used[i] = false;
        tempList.remove(tempList.size() - 1);
    }
}

除了上面说的剪枝方式，还有没有其他的剪枝方式呢，实际上是有的。就是当遍历到当前数字的时候，如果当前数字和数组中前一个数字一样，并且前一个数字被使用了，我们就跳过当前分支，也就是把当前分支给剪掉（和上面的相反）。如下图所示

这就是前面我们在讲590，回溯算法解正方形数组的数目中最后提到的，这两种剪枝方式都是可以的，一种是把整个大枝剪掉，一种是在每个大枝下面不停的剪小枝。很明显第一种剪枝效率更高一些，我们来看下代码

public List<List<Integer>> permuteUnique(int[] nums) {
    //先对数组进行排序，这样做目的是相同的值在数组中肯定是挨着的，
    //方便过滤掉重复的结果
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    //boolean数组，used[i]表示元素nums[i]是否被访问过
    boolean[] used = new boolean[nums.length];
    //执行回溯算法
    backtrack(nums, used, new ArrayList<>(), res);
    return res;
}

public void backtrack(int[] nums, boolean[] used, List<Integer> tempList, List<List<Integer>> res) {
    //如果数组中的所有元素都使用完了，类似于到了叶子节点，
    //我们直接把从根节点到当前叶子节点这条路径的元素加入
    //到集合res中
    if (tempList.size() == nums.length) {
        res.add(new ArrayList<>(tempList));
        return;
    }
    //遍历数组中的元素
    for (int i = 0; i < nums.length; i++) {
        //如果已经被使用过，则直接跳过
        if (used[i])
            continue;
        //注意，这里要剪掉重复的组合
        //如果当前元素和前一个一样，并且前一个被使用了，我们也跳过
        if (i > 0 && nums[i - 1] == nums[i] && used[i - 1])
            continue;
        //否则我们就使用当前元素，把他标记为已使用
        used[i] = true;
        //把当前元素nums[i]添加到tempList中
        tempList.add(nums[i]);
        //递归，类似于n叉树的遍历，继续往下走
        backtrack(nums, used, tempList, res);
        //递归完之后会往回走，往回走的时候要撤销选择
        used[i] = false;
        tempList.remove(tempList.size() - 1);
    }
}