题目

力扣题目链接

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

示例 1：

  1. 输入：nums = [1,1,2]
  2. 输出：
  3. [[1,1,2],
  4.  [1,2,1],
  5.  [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

思路

这道题目和 46. 全排列 的区别在与给定一个可包含重复数字的序列，要返回所有不重复的全排列。

这里又涉及到去重了。

在 40. 组合总和II 、90. 子集II 我们分别详细讲解了组合问题和子集问题如何去重。

那么排列问题其实也是一样的套路。

还要强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。

需要注意的是，在 491. 递增子序列 这个问题中，虽然要求去重，但却无法对元素进行排序。

还记得我们是如何解决这个问题的吗？

我们是通过在每一层的 for 循环之前定义了一个 used 数组作为哈希，用来记录本层元素是否重复使用。新的一层 used 都会重新定义（清空），所以 used 只负责本层。

而之前那些允许对元素进行排序时的去重，我们定义的 used 是一个全局变量，只收集当前分支下元素的使用情况，也就是树枝，而不是树层。此时如果 candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了 candidates[i - 1]，也就是说同一树层使用过 candidates[i - 1]。

也就是说，如果不允许对元素进行排序，我们就不能把 used 数组定义为全局变量了，因为 candidates[i] 不一定会等于 candidates[i - 1]，自然 used[i - 1] 的状态就没有参考价值了。

我以示例中的 [1,1,2]为例 （为了方便举例，已经排序）抽象为一棵树，去重过程如图：
image.png

图中我们对同一树层，前一位（也就是 nums[i-1] ）如果使用过，那么就进行去重。

一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。

在 46. 全排列 中已经详解讲解了排列问题的写法，在 40. 组合总和II 、90. 子集II 中详细讲解的去重的写法，所以这次我就不用回溯三部曲分析了，基本上可以直接写出答案了。

拓展

大家发现，去重最为关键的代码为：

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
    continue;
}

如果改成 used[i - 1] == true， 也是正确的!，去重代码如下：

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {
    continue;
}

这是为什么呢，就是上面我刚说的，如果要对树层中前一位去重，就用 used[i - 1] == false ，如果要对树枝前一位去重用 used[i - 1] == true 。

对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！

这么说是不是有点抽象？

来来来，我就用输入: [1,1,1] 来举一个例子。

树层上去重(used[i - 1] == false)，的树形结构如下：
image.png

树枝上去重（used[i - 1] == true）的树型结构如下：
image.png

大家应该很清晰的看到，树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。

答案

Java

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    int[] nums = null;
    boolean[] used = null; // 本题允许对元素进行排序，所以我们可以把 used 数组定义为全局变量

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);

        this.nums = nums;
        used = new boolean[nums.length];

        backtracking();

        return result;
    }

    void backtracking() {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // used[i - 1] == true，说明同一树枝 nums[i - 1] 使用过
            // used[i - 1] == false，说明同一树层 nums[i - 1] 使用过
            // 如果同一树层 nums[i - 1] 使用过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }

            // 如果同一树枝 nums[i] 没使用过开始处理
            if (used[i] == false) {
                path.add(nums[i]);
                // 标记同一树枝 nums[i] 使用过，防止同一树支重复使用
                used[i] = true;

                backtracking();

                // 回溯
                path.removeLast();
                used[i] = false;
            }
        }
    }
}

REF

https://programmercarl.com/0047.全排列II.html
https://leetcode-cn.com/problems/permutations-ii/