## 题目地址

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]
]
``````

## 思路

``````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;
}
}
};

``````

``````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

``````

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

``````

[[1,2,2], [2,1,2], [2,2,1], [2,2,1], [2,1,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

``````

``````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);
}
}
};

``````

``````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

``````

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

``````

``````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

``````

``````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());
}
};

``````

``````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;
}
};
``````

## 关键点解析

• 回溯法
• 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
``````

评论
0 评论