「力扣」第 47 题：全排列 II

递归回溯算法树形问题深度优先遍历

专题 14：回溯算法

发布日期: 2018-02-11

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

示例：
输入: [1, 1, 2]
输出:
[
  [1, 1, 2],
  [1, 2, 1],
  [2, 1, 1]
]

思路：

这一题在“全排列” 的基础上增加了元素可重复这一条件，但要求返回的结果又不能有重复元素；
如果依然按照上一题的方去做，就需要在结果集中去重。但是问题又来了，这些结果集的元素是一个又一个列表，对列表去重不像用哈希表对基本元素去重那样容易；
如果实在要比较两个列表是否一样，一个很显然的办法就是分别排序，然后逐个比对；
既然一定要排序，可以在搜索之前就对候选数组排序，一旦发现这一支搜索下去可能搜索到重复元素，就停止搜索，这个思想是解决这个问题的核心。

那么在候选数组有序的前提下，什么时候会发生重复呢？我们依然是看画出的树形图，模拟一下深度优先遍历的过程。

在这里插入图片描述

重复的搜索发生在这一轮考虑的选择和上一轮一样的时候，并且上一轮搜索的那个值因为在回退的过程中，刚刚被撤销，应该剪去的是这样的枝叶。

Java 代码：

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

public class Solution {

    public List<List<Integer>> permuteUnique(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        // 排序（升序或者降序都可以），为了剪枝方便
        Arrays.sort(nums);

        boolean[] used = new boolean[len];
        // 使用 Deque 是 Java 官方 Stack 类的建议
        Deque<Integer> path = new ArrayDeque<>(len);
        dfs(nums, len, 0, used, path, res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth, boolean[] used, Deque<Integer> path, List<List<Integer>> res) {
        if (depth == len) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < len; ++i) {
            if (used[i]) {
                continue;
            }

            // 剪枝条件，i > 0 是为了保证 nums[i - 1] 有意义
            // used[i - 1] 是因为 nums[i - 1] 在回退的过程中刚刚被撤销选择
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }

            path.addLast(nums[i]);
            used[i] = true;

            dfs(nums, len, depth + 1, used, path, res);

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

说明：这里重点是想清楚为什么是 used[i - 1] == false （写作 !used[i] 更好，这里只是为了可读性不写成这样）。如果写成 used[i - 1] == true 也可以剪枝，代码依然可以通过，但是剪枝的思路很不自然，具体细节可以参考我在「力扣」第 47 题：全排列 II 写的题解：回溯搜索 + 剪枝。

总结

以下几点是对上面介绍的知识的概括，没有写得很具体，留下一些空间给读者思考。如果有说错，或者是造成歧义的地方，欢迎大家与我交流。

回溯算法是一种深度优先遍历的搜索算法，本质上是在一个树形问题上进行遍历的算法；
如果使用广度优先遍历，我们得手动编创建队列、把状态变量封装成结点类，更要命的是，由于广度优先遍历是层序遍历的关系，到下一层的时候，「状态变量」会发生「突变」，因此就不能使用一个状态变量完成搜索任务；
而深度优先遍历，由于不同的状态变量在栈中出栈和入栈的结果下，它们的状态是相邻的，因此状态变化的消耗特别少，因此全程可以使用一个状态变量完成所有状态的搜索；
并且借助递归方法，我们不用手动编写栈，并且把需要的状态变量设计在递归方法的参数里即可，这一点和上一点是深度优先遍历可以成为强大的搜索算法的原因；
回溯算法本质上是遍历算法，因此复杂度一般而言较高，但是在一些问题中，我们可以提前发现某些分支无需遍历，应该跳过，这一步操作称之为“剪枝”。