题目地址(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] 为例，如果第一次选取了第一个 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，那么永远无法取到三个数，便形成了一个不可行解。
关键点解析
代码
语言支持: 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;
}
};
相关题目
