Skip to content

Latest commit

 

History

History
169 lines (135 loc) · 5 KB

47.permutations-ii.md

File metadata and controls

169 lines (135 loc) · 5 KB
Raw

题目地址(47. 全排列 II)

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

题目描述

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

示例:

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

前置知识

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

回溯的基本思路清参考上方的回溯专题。

这道题和第 46 题不一样的点在于其有重复元素。比如题目给的 [1,1,2]。

如果按照 46 题的解法，那么就会有重复的排列。 回顾一下 46 题我们的逻辑。以 [1,1,2] 为例，我们的逻辑是：

  • 先从 [1,1,2] 选取一个数。
  • 然后继续从 [1,1,2] 选取一个数，并且这个数不能是已经选取过的数。
  • 重复这个过程直到选取的数字达到了 3。

如果继续沿用上面的逻辑，那么我们是永远无法拿到全部三个数字的，因此我们的逻辑需要变化。

这里我的算法是记录每一个被选取的索引，而不是值，这就保证了同一个数字不会被选取多次，并且可以选取所有数字了。

不过这还是有一个问题。 仍然以 [1,1,2] 为例，如果第一次选取了第一个 1，第二次选取了第二个 1，这就产生了一个组合 [1,1,2]。 如果继续第一次选取了第二个 1，而第二次选取了第一个 1，那么又会产生组合 [1,1,2]，可以看出这两个组合是重复的。（题目认为这两种情况应该算一种）

一个解决方案是对 nums 进行一次排序，并规定如果 i > 0 and nums[i] == nums[i - 1] and visited[i - 1]， 则不进行选取即可。

经过这样的处理，每次实际上都是从后往前依次重复的数。仍然以上面的 [1,1,2] 为例。[1,1,2] 这个排列一定是先取的第二个 1，再取第一个 1，最后取的 2。这样可以避免重复的原因在于：如果先取的第一个 1，那么永远无法取到三个数，便形成了一个不可行解。

关键点解析

  • 回溯法
  • backtrack 解题公式

代码

  • 语言支持: Javascript，Python3, CPP

JS Code:

/*
 * @lc app=leetcode id=47 lang=javascript
 *
 * [47] Permutations II
 */
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; // 同一个数字不能用两次
    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 backtrack(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)
                    backtrack(left_nums, p_list)
        backtrack(nums, [])
        return res

CPP Code:

class Solution {
private:
  vector<vector<int>> ans;
  void permute(vector<int> nums, int start) {
    if (start == nums.size() - 1) {
      ans.push_back(nums);
      return;
    }
    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);
    }
  }
public:
  vector<vector<int>> permuteUnique(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    permute(nums, 0);
    return ans;
  }
};

相关题目