0047. 全排列 II
题目地址(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 resCPP 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; }};相关题目
最后更新于
这有帮助吗？