LeetCode-47. 全排列 II

问题地址

LeetCode每日一题/2020-09-18

LeetCode47. 全排列 II

问题描述

规则

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

示例

• 示例1

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

解析

解题思路

• 根据题目规则本题有两点约束：
  • 数字不可以被重复选择；
  • 找到的排列不能重复，由于本题所给的输入中包含重复数字，故[1_{(1)},1_{(2)},2]与[1_{(2)},1_{(1)},2]属重复排列；

数据操作分析

• 本题对排列组合结果的顺序没有要求，我们为了后边去重更方便首先对给定数组排序,对于排序后的数组进行全排列时，使用如下规则对重复排列去重：
  • $nums[i] = [numsi-1]$；
  • $visited[i-1] = true$；
• 对于第一条约束我们需要判断 visited[i]=true；
• 由于题目要求返回所有符合条件的全排列，所以我们在找到1个符合要求的全排列之后需要要撤销当前最新做的选择，回到选择前的状态，去选别的选项，切入别的搜索分支；

复杂度分析

编码实现

/**
 * LeetCode0047
 */
public class LeetCode0047_Permutationsii {
    boolean[] visted;
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        visted = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(res, tmp, nums, 0);
        return res;
    }

    private void dfs(List<List<Integer>> res, List<Integer> tmp, int[] nums, int index) {
        if (index == nums.length) {
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visted[i] || (i > 0 && nums[i] == nums[i - 1] && !visted[i - 1])) continue;
            tmp.add(nums[i]);
            visted[i] = true;
            dfs(res, tmp, nums, index + 1);
            visted[i] = false;
            tmp.remove(index);
        }
    }
}

官方解法

方法一：搜索回溯

思路：

• 此题是「46. 全排列」的进阶，序列中包含了重复的数字，要求我们返回不重复的全排列，那么我们依然可以选择使用搜索回溯的方法来做。
• 我们将这个问题看作有 n 个排列成一行的空格，我们需要从左往右依次填入题目给定的 n 个数，每个数只能使用一次。那么很直接的可以想到一种穷举的算法，即从左往右每一个位置都依此尝试填入一个数，看能不能填完这 n 个空格，在程序中我们可以用「回溯法」来模拟这个过程。
• 我们定义递归函数 backtrack(idx, perm) 表示当前排列为 \textit{perm}，下一个待填入的位置是第 \textit{idx} 个位置（下标从 0 开始）。那么整个递归函数分为两个情况：
  • 如果 \textit{idx}= =n，说明我们已经填完了 n 个位置，找到了一个可行的解，我们将 \textit{perm} 放入答案数组中，递归结束。
  • 如果 \textit{idx}<n，我们要考虑第 \textit{idx} 个位置填哪个数。根据题目要求我们肯定不能填已经填过的数，因此很容易想到的一个处理手段是我们定义一个标记数组 \textit{vis} 来标记已经填过的数，那么在填第 \textit{idx} 个数的时候我们遍历题目给定的 n 个数，如果这个数没有被标记过，我们就尝试填入，并将其标记，继续尝试填下一个位置，即调用函数 backtrack(idx + 1, perm)。搜索回溯的时候要撤销该个位置填的数以及标记，并继续尝试其他没被标记过的数。
• 但题目解到这里并没有满足「全排列不重复」 的要求，在上述的递归函数中我们会生成大量重复的排列，因为对于第 \textit{idx} 的位置，如果存在重复的数字 i，我们每次会将重复的数字都重新填上去并继续尝试导致最后答案的重复，因此我们需要处理这个情况。
• 要解决重复问题，我们只要设定一个规则，保证在填第 \textit{idx} 个数的时候重复数字只会被填入一次即可。而在本题解中，我们选择对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」，即如下的判断条件：

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

• 这个判断条件保证了对于重复数的集合，一定是从左往右逐个填入的。
• 假设我们有 3 个重复数排完序后相邻，那么我们一定保证每次都是拿从左往右第一个未被填过的数字，即整个数组的状态其实是保证了 [未填入，未填入，未填入] 到 [填入，未填入，未填入]，再到 [填入，填入，未填入]，最后到 [填入，填入，填入] 的过程的，因此可以达到去重的目标。

复杂度分析

1. 时间复杂度：O(n\times n!)，其中 n 为序列的长度。

– 算法的复杂度首先受 backtrack 的调用次数制约，backtrack 的调用次数为 \sum_{k = 1}^{n}{P(n, k)} 次，其中 P(n, k) = \frac{n!}{(n – k)!} = n (n – 1) … (n – k + 1)，该式被称作 $n$ 的 $k -$ 排列，或者部分排列。
– 根据以下算式可推到 backtrack 的调用次数是 O(n!) 的:

\sum_{k = 1}^{n}{P(n, k)} = n! + \frac{n!}{1!} + \frac{n!}{2!} + \frac{n!}{3!} + … + \frac{n!}{(n-1)!}<2n! + \frac{n!}{2} + \frac{n!}{2^2} + \frac{n!}{2^{n-2}}<3n!

• 对于 backtrack 调用的每个叶结点（最坏情况下没有重复数字共 n! 个），我们需要将当前答案使用 O(n) 的时间复制到答案数组中，相乘得时间复杂度为 O(n \times n!)。因此时间复杂度为 O(n \times n!)。

2.空间复杂度：O(n)。我们需要 O(n) 的标记数组，同时在递归的时候栈深度会达到 O(n)，因此总空间复杂度为 O(n + n)=O(2n)=O(n)。

编码实现

class Solution {
    boolean[] vis;

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans, 0, perm);
        return ans;
    }

    public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.add(nums[i]);
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = false;
            perm.remove(idx);
        }
    }
}

精彩评论

跳转地址1：回溯搜索 + 剪枝（Java、Python）

• 这一题在「力扣」第 46 题： 全排列 的基础上增加了 序列中的元素可重复 这一条件，但要求：返回的结果又不能有重复元素。
  

思路

• 在遍历的过程中，一边遍历一遍检测，在一定会产生重复结果集的地方剪枝。一个比较容易想到的办法是在结果集中去重。但是问题来了，这些结果集的元素是一个又一个列表，对列表去重不像用哈希表对基本元素去重那样容易。
• 如果要比较两个列表是否一样，一个容易想到的办法是对列表分别排序，然后逐个比对。既然要排序，我们就可以 在搜索之前就对候选数组排序，一旦发现某个分支搜索下去可能搜索到重复的元素就停止搜索，这样结果集中不会包含重复列表。
• 画出树形结构如下：重点想象深度优先遍历在这棵树上执行的过程，哪些地方遍历下去一定会产生重复，这些地方的状态的特点是什么？对比图中标注 ① 和 ② 的地方。相同点是：这一次搜索的起点和上一次搜索的起点一样。不同点是：
  • 标注 ① 的地方上一次搜索的相同的数刚刚被撤销；
  • 标注 ② 的地方上一次搜索的相同的数刚刚被使用。
    
• 产生重复结点的地方，正是图中标注了「剪刀」，且被绿色框框住的地方。大家也可以把第 2 个 1 加上 ‘ ，即 [1, 1’, 2] 去想象这个搜索的过程。只要遇到起点一样，就有可能产生重复。这里还有一个很细节的地方：
  • 在图中 ② 处，搜索的数也和上一次一样，但是上一次的 1 还在使用中；
  • 在图中 ① 处，搜索的数也和上一次一样，但是上一次的 1 刚刚被撤销，正是因为刚被撤销，下面的搜索中还会使用到，因此会产生重复，剪掉的就应该是这样的分支。
• 代码实现方面，在第 46 题的基础上，要加上这样一段代码：

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

• 这段代码就能检测到标注为 ① 的两个结点，跳过它们。注意：这里 used[i – 1] 不加 !，测评也能通过。有兴趣的朋友可以想一想这是为什么。建议大家做这样几个对比实验：
  • 干脆就不写 !used[i – 1] 结果是什么样？
  • 写 used[i – 1] 结果是什么，代码又是怎样执行的。这里给出的结论是：!used[i – 1] 这样的剪枝更彻底。附录会分析原因。

复杂度分析：

• 重复元素越多，剪枝越多。但是计算复杂度的时候需要考虑最差情况。

1. 时间复杂度：O(N \times N!)，这里 N 为数组的长度。
2. 空间复杂度：O(N)。

编码实现

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]) {
                continue;
            }

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

            dfs(nums, len, depth + 1, used, path, res);
            // 回溯部分的代码，和 dfs 之前的代码是对称的
            used[i] = false;
            path.removeLast();
        }
    }
}

补充说明 写 used[i – 1] 代码正确，但是不推荐的原因

思路是根据深度优先遍历的执行流程，看一看那些状态变量（布尔数组 used）的值。
1、如果剪枝写的是：

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

那么，对于数组 [1, 1’, 1’’, 2]，回溯的过程如下：

得到的全排列是：[[1, 1′, 1”, 2], [1, 1′, 2, 1”], [1, 2, 1′, 1”], [2, 1, 1′, 1”]]。特点是：1、1’、1” 出现的顺序只能是 1、1’、1”。

2、如果剪枝写的是：

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

那么，对于数组 [1, 1’, 1’’, 2]，回溯的过程如下（因为过程稍显繁琐，所以没有画在一张图里）：
（1）先选第 1 个数字，有 4 种取法。

（2）对第 1 步的第 1 个分支，可以继续搜索，但是发现，没有搜索到合适的叶子结点。

（3）对第 1 步的第 2 个分支，可以继续搜索，但是同样发现，没有搜索到合适的叶子结点。

（4）对第 1 步的第 3 个分支，继续搜索发现搜索到合适的叶子结点。

（5）对第 1 步的第 4 个分支，继续搜索发现搜索到合适的叶子结点。

因此，used[i – 1] 前面加不加感叹号的区别仅在于保留的是相同元素的顺序索引，还是倒序索引。很明显，顺序索引（即使用 !used[i – 1] 作为剪枝判定条件得到）的递归树剪枝更彻底，思路也相对较自然。

跳转地址2：47. 全排列 II:【彻底理解排列中的去重问题】详解

思路

这道题目和46.全排列的区别在与给定一个可包含重复数字的序列，要返回所有不重复的全排列。这里就涉及到去重了。
要注意全排列是要取树的子节点的，如果是子集问题，就取树上的所有节点。
很多同学在去重上想不明白，其实很多题解也没有讲清楚，反正代码是能过的，感觉是那么回事，稀里糊涂的先把题目过了。
这个去重为什么很难理解呢，所谓去重，其实就是使用过的元素不能重复选取。 这么一说好像很简单！
但是什么又是“使用过”，我们把排列问题抽象为树形结构之后，“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。
没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。
那么排列问题，既可以在 同一树层上的“使用过”来去重，也可以在同一树枝上的“使用过”来去重！
理解这一本质，很多疑点就迎刃而解了。
首先把示例中的 [1,1,2]，抽象为一棵树，然后在同一树层上对nums[i-1]使用过的话，进行去重如图：

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

编码实现

class Solution {
private:
    vector<vector<int>> result;
    void backtracking (vector<int>& nums, vector<int>& vec, vector<bool>& used) {
        // 此时说明找到了一组
        if (vec.size() == nums.size()) {
            result.push_back(vec);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            // 这里理解used[i - 1]非常重要 
            // 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;
            }
            if (used[i] == false) {
                used[i] = true;
                vec.push_back(nums[i]);
                backtracking(nums, vec, used);
                vec.pop_back();
                used[i] = false;
            }
        }
    }

public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<bool> used(nums.size(), false);
        vector<int> vec;
        backtracking(nums, vec, used);
        return result;

    }
};

拓展

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

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 )，的树形结构如下：

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

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