本期例题（共两道）：

例题一，存在重复元素的子集问题：LeetCode 90 - Subsets II（Medium）

给定一组可能包含重复元素的整数 nums，返回所有可能的子集（幂集）。例如：

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

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

例题二，存在重复元素的全排列问题：LeetCode 47 - Permutations II（Medium）

给定一个可能重复的整数集合，返回其所有可能的全排列。例如：

• 输入：[1, 2, 2]
• 输出：

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

子集问题和全排列问题都是经典的回溯法问题，在前面的文章中都讲过详细的思路和题解。本期的例题是它们的变种，都是在输入中存在重复元素，要避免输出重复的结果。

这两道题目都考察的是回溯法的剪枝策略。在上一篇文章中我们已经讲过了 $P(n, k)$ 和 $C(n, k)$ 中的剪枝。出现重复元素时的剪枝思路也比较类似。我们要根据题目的性质，思考如何去除重复的结果，以及如何将去重实现为决策树上的剪枝。

这篇文章将会包含子集（Subsets）、排列（Permutations）、组合（Combinations）问题的去重策略、剪枝方案与题解代码。

有重复元素的子集问题

第三讲《从二叉树遍历到回溯算法》的文章中讲到了子集问题的决策树。这里我们来回顾一下，回溯法一共进行 $n$ 次决策， 每次决策有两个分支，决定第 $i$ 个元素是否放入子集。以 $[1, 2, 3]$ 为例，决策树的形状如下图所示。

题解代码如下。注意在注释中写清楚什么是候选集合，这样能让思路更清晰。

public List<List<Integer>> subsets(int[] nums) {
    Deque<Integer> current = new ArrayDeque<>(nums.length);
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, current, res);
    return res;
}

// 候选集合: nums[k..N)
void backtrack(int[] nums, int k, Deque<Integer> current, List<List<Integer>> res) {
    if (k == nums.length) {
        res.add(new ArrayList<>(current));
        return;
    }

    // 不选择第 k 个元素
    backtrack(nums, k+1, current, res);

    // 选择第 k 个元素
    current.addLast(nums[k]);
    backtrack(nums, k+1, current, res);
    current.removeLast();
}

那么，当输入中有重复元素时，如何去除重复的结果呢？方法仍然是剪枝。

在上一篇文章中我们计算组合 $C(n,k)$ 的时候就用到了剪枝的思想。为了得到升序的结果，我们从候选集合中选出元素 $x$ 的时候，会将集合中比 $x$ 小的元素标记为无效。今天我们要讨论的重复元素的问题，也是通过标记无效元素来剪枝的。

我们以输入 $[1, 2, 2, 2]$ 为例，$[1, 2, 2]$ 是它的一个子集。为了区分重复的 $2$，我们将三个 $2$ 记为 $2_1$、$2_2$、$2_3$，那么子集 $[1, 2, 2]$ 有可能是 $[1, 2_1, 2_2]$、$[1, 2_1, 2_3]$ 或者 $[1, 2_2, 2_3]$。这三个结果显然是重复的，我们只需要保留其中的一个。如何做剪枝呢？

我们可以规定：在一连串的 $2$ 里面，如果第一个 $2$ 没有放入子集，那么后面的 $2$ 都不能放入子集。也就是说，如果不选择 $2_1$，就不能选择 $2_2$ 或 $2_3$。这样要想在结果中出现两个 $2$，只可能是 $2_1$ 和 $2_2$。去重成功！对应的决策树剪枝情况如下图所示。

如何将这段剪枝逻辑翻译成代码呢？需要做到两点：

1. 在回溯之前，预先将数组中所有元素排序，这样数组中相等的元素就都是相邻的；
2. 每次对于元素 $x$ 做决策时，如果不选择候选元素 $x$，那么 $x$ 后面紧跟着的相等元素也都跳过，不再选择。

以下是题解代码。

public List<List<Integer>> subsetsWithDup(int[] nums) {
    // 对元素排序，保证相等的元素相邻
    Arrays.sort(nums);
    Deque<Integer> current = new ArrayDeque<>(nums.length);
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, current, res);
    return res;
}

// 候选集合: nums[k..N)
void backtrack(int[] nums, int k, Deque<Integer> current, List<List<Integer>> res) {
    if (k == nums.length) {
        res.add(new ArrayList<>(current));
        return;
    }

    // 选择 nums[k]
    current.addLast(nums[k]);
    backtrack(nums, k+1, current, res);
    current.removeLast();

    // 不选择 nums[k]
    // 将后续和 nums[k] 相等的元素 nums[k..j) 都跳过
    int j = k;
    while (j < nums.length && nums[j] == nums[k]) {
        j++;
    }
    backtrack(nums, j, current, res);
}

有重复元素的全排列问题

有重复元素的全排列问题，思路和子集问题非常像。只不过由于回溯方式的不同，代码上显得不太一样。

我们还是以输入 $[1, 2, 2, 2]$ 为例，其中的三个 $2$ 记为 $2_1$、$2_2$、$2_3$。$[1, 2, 2, 2]$ 是它的一个排列。但这个排列可能是 $[1, 2_1, 2_2, 2_3]$、$[1, 2_1, 2_3, 2_2]$、$[1, 2_2, 2_1, 2_3]$、$[1, 2_2, 2_3, 2_1]$、$[1, 2_3, 2_1, 2_2]$ 或者 $[1, 2_3, 2_2, 2_1]$，共 6 种可能。我们该如何做剪枝，只保留其中一种结果呢？

我们可以规定：如果有多个 $2$ 候选，那么只能选第一个 $2$，后面的 $2$ 此次不能选。也就是说，三个 $2$ 只能先选 $2_1$，再选 $2_2$，最后选 $2_3$，只有排列 $2_1, 2_2, 2_3$ 才是合法的结果。去重成功！对应的决策树剪枝情况如下图所示。

不过对于全排列问题，我们不能通过对原数组排序来保证相等的元素一定相邻。在回溯的过程中会做各种元素的交换操作，打破原先的相邻关系。那么我们需要使用一个集合辅助判断候选元素是否是第一次出现。

以下是题解代码。

public List<List<Integer>> permuteUnique(List<Integer> nums) {
    List<Integer> current = new ArrayList<>(nums);
    List<List<Integer>> res = new ArrayList<>();
    backtrack(current, 0, res);
    return res;
}

// 已选集合 current[0..m)，候选集合 current[m..N)
void backtrack(List<Integer> current, int m, List<List<Integer>> res) {
    if (m == current.size()) {
        res.add(new ArrayList<>(current));
        return;
    }

    // 使用 set 辅助判断相等的候选元素是否已经出现过。
    Set<Integer> seen = new HashSet<>();
    for (int i = m; i < current.size(); i++) {
        int e = current.get(i);
        if (seen.contains(e)) {
            // 如果已经出现过相等的元素，则不选此元素
            continue;
        }
        seen.add(e);
        Collections.swap(current, m, i);
        backtrack(current, m+1, res);
        Collections.swap(current, m, i);
    }
}

有重复元素的组合问题

组合问题在 LeetCode 上并没有对应题目，不过出于讲解的完整性，我们不妨在子集问题、排列问题之后继续思考，有重复元素的组合问题该如何解决。

我们在上一篇文章中讲解过，组合问题 $C(n,k)$ 可以从排列问题 $P(n,k)$ 去重之后得来，也可以看成是子集问题的变种，取大小为 $k$ 的子集。那么，有重复元素的组合问题，我们也可以从有重复元素的排列问题、子集问题稍加变化得到解法。

不过，基于排列问题的思路本身已经比较复杂，需要考虑已选元素、候选元素和失效元素。再加上剪枝的话，思路会更加复杂。所以，我们使用基于子集问题的方法，并加入和子集问题一样的去重策略。以输入 $[1,1,3,4]$ 为例，对应的决策树如下图所示。

具体的代码这里就不展示了，请各位读者自行在子集问题的题解代码基础上修改得到组合问题的代码。

总结

我们在一篇文章中讲解了子集问题、排列问题、组合问题的有重复元素版本。可以看到，它们的解题思路都非常类似。总结起来，这一类需要去重的回溯法题目都可以遵循这几个步骤：

1. 首先把无重复元素版本的题目写对（这很重要！）；
2. 思考剪枝策略；
3. 根据代码的特点加入特定的剪枝判断，可以使用预排序，或是利用数据结构。

本期例题的题解代码看似容易，但还是需要多加练习并熟练为好。回溯法问题的难度除了在解题思路，还在于如何写出清晰、移动、无 bug 的代码。多做练习，精简代码，这是解好回溯法问题的诀窍。