daily leetcode - permutations-ii - ! - LouisLan的学习简记

2020-02-06 / 2020-02-06 / daily-leetcode

daily leetcode - permutations-ii - !

题目地址

https://leetcode.com/problems/permutations-ii/

题目描述

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

思路

这道题是之前那道 Permutations 的延伸，由于输入数组有可能出现重复数字，如果按照之前的算法运算，会有重复排列产生，我们要避免重复的产生，在递归函数中要判断前面一个数和当前的数是否相等，如果相等，且其对应的 visited 中的值为 1，当前的数字才能使用（下文中会解释这样做的原因），否则需要跳过，这样就不会产生重复排列了，代码如下：

解法一：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> out, visited(nums.size(), 0);
        sort(nums.begin(), nums.end());
        permuteUniqueDFS(nums, 0, visited, out, res);
        return res;
    }
    void permuteUniqueDFS(vector<int>& nums, int level, vector<int>& visited, vector<int>& out, vector<vector<int>>& res) {
        if (level >= nums.size()) {res.push_back(out); return;}
        for (int i = 0; i < nums.size(); ++i) {
            if (visited[i] == 1) continue;
            if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == 0) continue;
            visited[i] = 1;
            out.push_back(nums[i]);
            permuteUniqueDFS(nums, level + 1, visited, out, res);
            out.pop_back();
            visited[i] = 0;
        }
    }
};

在使用上面的方法的时候，一定要能弄清楚递归函数的 for 循环中两个 if 的剪枝的意思。在此之前，要弄清楚 level 的含义，这里用数组 out 来拼排列结果，level 就是当前已经拼成的个数，其实就是 out 数组的长度。我们看到，for 循环的起始是从 0 开始的，而本题的解法二，三，四都是用了一个 start 变量，从而 for 循环都是从 start 开始，一定要分清楚 start 和本解法中的 level 的区别。由于递归的 for 都是从 0 开始，难免会重复遍历到数字，而全排列不能重复使用数字，意思是每个 nums 中的数字在全排列中只能使用一次（当然这并不妨碍 nums 中存在重复数字）。不能重复使用数字就靠 visited 数组来保证，这就是第一个 if 剪枝的意义所在。关键来看第二个 if 剪枝的意义，这里说当前数字和前一个数字相同，且前一个数字的 visited 值为 0 的时候，必须跳过。这里的前一个数 visited 值为 0，并不代表前一个数字没有被处理过，也可能是递归结束后恢复状态时将 visited 值重置为 0 了，实际上就是这种情况，下面打印了一些中间过程的变量值，如下所示：

level = 0, i = 0 => out: {}
level = 1, i = 0 => out: {1 } skipped 1
level = 1, i = 1 => out: {1 }
level = 2, i = 0 => out: {1 2 } skipped 1
level = 2, i = 1 => out: {1 2 } skipped 1
level = 2, i = 2 => out: {1 2 }
level = 3 => saved  {1 2 2}
level = 3, i = 0 => out: {1 2 2 } skipped 1
level = 3, i = 1 => out: {1 2 2 } skipped 1
level = 3, i = 2 => out: {1 2 2 } skipped 1
level = 2, i = 2 => out: {1 2 2 } -> {1 2 } recovered
level = 1, i = 1 => out: {1 2 } -> {1 } recovered
level = 1, i = 2 => out: {1 } skipped 2
level = 0, i = 0 => out: {1 } -> {} recovered
level = 0, i = 1 => out: {}
level = 1, i = 0 => out: {2 }
level = 2, i = 0 => out: {2 1 } skipped 1
level = 2, i = 1 => out: {2 1 } skipped 1
level = 2, i = 2 => out: {2 1 }
level = 3 => saved  {1 2 2}
level = 3, i = 0 => out: {2 1 2 } skipped 1
level = 3, i = 1 => out: {2 1 2 } skipped 1
level = 3, i = 2 => out: {2 1 2 } skipped 1
level = 2, i = 2 => out: {2 1 2 } -> {2 1 } recovered
level = 1, i = 0 => out: {2 1 } -> {2 } recovered
level = 1, i = 1 => out: {2 } skipped 1
level = 1, i = 2 => out: {2 }
level = 2, i = 0 => out: {2 2 }
level = 3 => saved  {1 2 2}
level = 3, i = 0 => out: {2 2 1 } skipped 1
level = 3, i = 1 => out: {2 2 1 } skipped 1
level = 3, i = 2 => out: {2 2 1 } skipped 1
level = 2, i = 0 => out: {2 2 1 } -> {2 2 } recovered
level = 2, i = 1 => out: {2 2 } skipped 1
level = 2, i = 2 => out: {2 2 } skipped 1
level = 1, i = 2 => out: {2 2 } -> {2 } recovered
level = 0, i = 1 => out: {2 } -> {} recovered
level = 0, i = 2 => out: {} skipped 2

注意看这里面的 skipped 1 表示的是第一个 if 剪枝起作用的地方，skipped 2 表示的是第二个 if 剪枝起作用的地方。我们主要关心的是第二个 if 剪枝，看上方第一个蓝色标记的那行，再上面的红色一行表示在 level = 1, i = 1 时递归调用结束后，恢复到起始状态，那么此时 out 数组中只有一个 1，后面的 2 已经被 pop_back() 了，当然对应的 visited 值也重置为 0 了，这种情况下需要剪枝，当然不能再一次把 2 往里加，因为这种情况在递归中已经加入到结果 res 中了，所以到了 level = 1, i = 2 的状态时，nums[i] == nums[i-1] && visited[i-1] == 0 的条件满足了，剪枝就起作用了，这种重复的情况就被剪掉了。

还有一种比较简便的方法，在 Permutations 的基础上稍加修改，用 TreeSet 来保存结果，利用其不会有重复项的特点，然后在递归函数中 swap 的地方，判断如果 i 和 start 不相同，但是 nums[i] 和 nums[start] 相同的情况下跳过，继续下一个循环，参见代码如下：

解法二：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        set<vector<int>> res;
        permute(nums, 0, res);
        return vector<vector<int>> (res.begin(), res.end());
    }
    void permute(vector<int>& nums, int start, set<vector<int>>& res) {
        if (start >= nums.size()) res.insert(nums);
        for (int i = start; i < nums.size(); ++i) {
            if (i != start && nums[i] == nums[start]) continue;
            swap(nums[i], nums[start]);
            permute(nums, start + 1, res);
            swap(nums[i], nums[start]);
        }
    }
};

对于上面的解法，你可能会有疑问，我们不是在 swap 操作之前已经做了剪枝了么，为什么还是会有重复出现，以至于还要用 TreeSet 来取出重复呢。总感觉使用 TreeSet 去重复有点耍赖，可能并没有探究到本题深层次的内容。这是很好的想法，首先尝试将上面的 TreeSet 还原为 vector，并且在主函数调用递归之前给 nums 排个序（代码参见评论区三楼），然后测试一个最简单的例子：[1, 2, 2]，得到的结果为：

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

我们发现有重复项，那么剪枝究竟在做些什么，怎么还是没法防止重复项的产生！那个剪枝只是为了防止当 start = 1, i = 2 时，将两个 2 交换，这样可以防止 {1, 2, 2} 被加入两次。但是没法防止其他的重复情况，要闹清楚为啥，需要仔细分析一些中间过程，下面打印了一些中间过程的变量：

start = 0, i = 0 => {1 2 2} 
start = 1, i = 1 => {1 2 2} 
start = 2, i = 2 => {1 2 2} 
start = 3 => saved  {1 2 2}
start = 1, i = 2 => {1 2 2} skipped
start = 0, i = 1 => {1 2 2} -> {2 1 2}
start = 1, i = 1 => {2 1 2} 
start = 2, i = 2 => {2 1 2} 
start = 3 => saved  {2 1 2}
start = 1, i = 2 => {2 1 2} -> {2 2 1}
start = 2, i = 2 => {2 2 1} 
start = 3 => saved  {2 2 1}
start = 1, i = 2 => {2 2 1} -> {2 1 2} recovered
start = 0, i = 1 => {2 1 2} -> {1 2 2} recovered
start = 0, i = 2 => {1 2 2} -> {2 2 1}
start = 1, i = 1 => {2 2 1} 
start = 2, i = 2 => {2 2 1} 
start = 3 => saved  {2 2 1}
start = 1, i = 2 => {2 2 1} -> {2 1 2}
start = 2, i = 2 => {2 1 2} 
start = 3 => saved  {2 1 2}
start = 1, i = 2 => {2 1 2} -> {2 2 1} recovered
start = 0, i = 2 => {2 2 1} -> {1 2 2} recovered

问题出在了递归调用之后的还原状态，参见上面的红色的两行，当 start = 0, i = 2 时，nums 已经还原到了 {1, 2, 2} 的状态，此时 nums[start] 不等于 nums[i]，剪枝在这已经失效了，那么交换后的 {2, 2, 1} 还会被存到结果 res 中，而这个状态在之前就已经存过了一次。

注意到当 start = 0, i = 1 时，nums 交换之后变成了 {2, 1, 2}，如果能保持这个状态，那么当 start = 0, i = 2 时，此时 nums[start] 就等于 nums[i] 了，剪枝操作就可以发挥作用了。怎么才能当递归结束后，不还原成为交换之前的状态的呢？答案就是不进行还原，这样还是能保存为之前交换后的状态。只是将最后一句 swap(nums[i], nums[start]) 删掉是不行的，因为递归函数的参数 nums 是加了&号，就表示引用了，那么之前调用递归函数之前的 nums 在递归函数中会被修改，可能还是无法得到我们想要的顺序，所以要把递归函数的 nums 参数的&号也同时去掉才行，参见代码如下：

解法三：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        permute(nums, 0, res);
        return res;
    }
    void permute(vector<int> nums, int start, vector<vector<int>>& res) {
        if (start >= nums.size()) res.push_back(nums);
        for (int i = start; i < nums.size(); ++i) {
            if (i != start && nums[i] == nums[start]) continue;
            swap(nums[i], nums[start]);
            permute(nums, start + 1, res);
        }
    }
};

好，再测试下 [1, 2, 2] 这个例子，并且把中间变量打印出来：

start = 0, i = 0 => {1 2 2} 
start = 1, i = 1 => {1 2 2} 
start = 2, i = 2 => {1 2 2} 
start = 3 => saved  {1 2 2}
start = 1, i = 2 => {1 2 2} skipped
start = 0, i = 1 => {1 2 2} -> {2 1 2}
start = 1, i = 1 => {2 1 2} 
start = 2, i = 2 => {2 1 2} 
start = 3 => saved  {2 1 2}
start = 1, i = 2 => {2 1 2} -> {2 2 1}
start = 2, i = 2 => {2 2 1} 
start = 3 => saved  {2 2 1}
start = 1, i = 2 => {2 2 1} recovered
start = 0, i = 1 => {2 1 2} recovered
start = 0, i = 2 => {2 1 2} skipped

明显发现短了许多，说明剪枝发挥了作用，看上面红色部分，当 start = 0, i = 1 时，递归函数调用完了之后，nums 数组保持了 {2, 1, 2} 的状态，那么到 start = 0, i = 2 的时候，nums[start] 就等于 nums[i] 了，剪枝操作就可以发挥作用了。

这时候你可能会想，调用完递归不恢复状态，感觉怪怪的，跟哥的递归模版不一样啊，容易搞混啊，而且一会加&号，一会不加的，这尼玛谁能分得清啊。别担心，I gotcha covered! 好，既然还是要恢复状态的话，就只能从剪枝入手了，原来那种 naive 的剪枝方法肯定无法使用，矛盾的焦点还是在于，当 start = 0, i = 2 时，nums 被还原成了 start = 0, i = 1 的交换前的状态 {1, 2, 2}，这个状态已经被处理过了，再去处理一定会产生重复，怎么才知道这被处理过了呢，当前的 i = 2，需要往前去找是否有重复出现，由于数组已经排序过了，如果有重复，那么前面数一定和当前的相同，所以用一个 while 循环，往前找和 nums[i] 相同的数字，找到了就停下，当然如果小于 start 了也要停下，那么如果没有重复数字的话，j 一定是等于 start-1 的，那么如果不等于的话，就直接跳过就可以了，这样就可以去掉所有的重复啦，参见代码如下：

解法四：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        permute(nums, 0, res);
        return res;
    }
    void permute(vector<int>& nums, int start, vector<vector<int>>& res) {
        if (start >= nums.size()) res.push_back(nums);
        for (int i = start; i < nums.size(); ++i) {
            int j = i - 1;
            while (j >= start && nums[j] != nums[i]) --j;
            if (j != start - 1) continue;
            swap(nums[i], nums[start]);
            permute(nums, start + 1, res);
            swap(nums[i], nums[start]);
        }
    }
};

同样，我们再测试下 [1, 2, 2] 这个例子，并且把中间变量打印出来：

start = 0, i = 0 => {1 2 2} , j = -1
start = 1, i = 1 => {1 2 2} , j = 0
start = 2, i = 2 => {1 2 2} , j = 1
start = 3 => saved  {1 2 2}
start = 1, i = 2 => {1 2 2} skipped, j = 1
start = 0, i = 1 => {1 2 2} -> {2 1 2}, j = -1
start = 1, i = 1 => {2 1 2} , j = 0
start = 2, i = 2 => {2 1 2} , j = 1
start = 3 => saved  {2 1 2}
start = 1, i = 2 => {2 1 2} -> {2 2 1}, j = 0
start = 2, i = 2 => {2 2 1} , j = 1
start = 3 => saved  {2 2 1}
start = 1, i = 2 => {2 2 1} -> {2 1 2} recovered
start = 0, i = 1 => {2 1 2} -> {1 2 2} recovered
start = 0, i = 2 => {1 2 2} skipped, j = 1

到 start = 0, i = 2 的时候，j 此时等于 1 了，明显不是 start-1，说明有重复了，直接 skip 掉，这样剪枝操作就可以发挥作用了。

之前的 Permutations 中的解法三也可以用在这里，只不过需要借助 TreeSet 来去重复，博主还未想出其他不用集合的去重复的方法，哪位看官大神们知道的话，请一定要留言告知博主，参见代码如下：

解法五：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        if (nums.empty()) return vector<vector<int>>(1, vector<int>());
        set<vector<int>> res;
        int first = nums[0];
        nums.erase(nums.begin());
        vector<vector<int>> words = permuteUnique(nums);
        for (auto &a : words) {
            for (int i = 0; i <= a.size(); ++i) {
                a.insert(a.begin() + i, first);
                res.insert(a);
                a.erase(a.begin() + i);
            }
        }   
        return vector<vector<int>> (res.begin(), res.end());
    }
};

之前的 Permutations 中的解法四博主没法成功修改使其可以通过这道题，即便是将结果 res 用 TreeSet 来去重复，还是不对。同样，哪位看官大神们知道的话，请一定要留言告知博主。不过之前的 Permutations 中的解法五却可以原封不动的搬到这道题来，看来自带的 next_permutation() 函数就是叼啊，自带去重复功能，叼叼叼！参见代码如下：

解法六：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        res.push_back(nums);
        while (next_permutation(nums.begin(), nums.end())) {
            res.push_back(nums);
        }
        return res;
    }
};

思路 2

这道题目是求集合，并不是求极值，因此动态规划不是特别切合，因此我们需要考虑别的方法。

这种题目其实有一个通用的解法，就是回溯法。
网上也有大神给出了这种回溯法解题的
通用写法，这里的所有的解法使用通用方法解答。
除了这道题目还有很多其他题目可以用这种通用解法，具体的题目见后方相关题目部分。

我们先来看下通用解法的解题思路，我画了一张图：

mark

通用写法的具体代码见下方代码区。

关键点解析

回溯法
backtrack 解题公式

代码

语言支持： JavaScript，Python3

/*
 * @lc app=leetcode id=47 lang=javascript
 *
 * [47] Permutations II
 *
 * https://leetcode.com/problems/permutations-ii/description/
 *
 * algorithms
 * Medium (39.29%)
 * Total Accepted:    234.1K
 * Total Submissions: 586.2K
 * Testcase Example:  '[1,1,2]'
 *
 * Given a collection of numbers that might contain duplicates, return all
 * possible unique permutations.
 *
 * Example:
 *
 *
 * Input: [1,1,2]
 * Output:
 * [
 * ⁠ [1,1,2],
 * ⁠ [1,2,1],
 * ⁠ [2,1,1]
 * ]
 *
 *
 */
function backtrack(list, nums, tempList, visited) {
  if (tempList.length === nums.length) return list.push([...tempList]);
  for (let i = 0; i < nums.length; i++) {
    // 和46.permutations的区别是这道题的nums是可以重复的
    // 我们需要过滤这种情况
    if (visited[i]) continue; // 不能用tempList.includes(nums[i])了，因为有重复
    // visited[i - 1] 这个判断容易忽略
    if (i > 0 && nums[i] === nums[i - 1] && visited[i - 1]) continue;

    visited[i] = true;
    tempList.push(nums[i]);
    backtrack(list, nums, tempList, visited);
    visited[i] = false;
    tempList.pop();
  }
}
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
  const list = [];
  backtrack(list, nums.sort((a, b) => a - b), [], []);
  return list;
};

Python3 code:

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        """与46题一样，当然也可以直接调用itertools的函数，然后去重"""
        return list(set(itertools.permutations(nums)))
      
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        """自己写回溯法，与46题相比，需要去重"""
        # 排序是为了去重
        nums.sort()
        res = []
        def _backtrace(nums, pre_list):
            if len(nums) <= 0:
                res.append(pre_list)
            else:
                for i in range(len(nums)):
                    # 如果是同样的数字，则之前一定已经生成了对应可能
                    if i > 0 and nums[i] == nums[i-1]:
                        continue
                    p_list = pre_list.copy()
                    p_list.append(nums[i])
                    left_nums = nums.copy()
                    left_nums.pop(i)
                    _backtrace(left_nums, p_list)
        _backtrace(nums, [])
        return res