给定一个可包含重复数字的序列,返回所有不重复的全排列。
示例:
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
题目标签:Backtracking
题目链接:LeetCode / LeetCode中国
这个如果用Python自带的itertools.permutations
就会有重复,所以,还是要会自己实现。简单的做法就是递归,难点主要在于不重复。思路是:先排序,然后根据上一个组合来判断是否重复。递归注意递归出口条件。
Language | Runtime | Memory |
---|---|---|
python3 | 88 ms | N/A |
class Solution:
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if len(nums) == 0:
return []
if len(nums) == 1:
return [nums]
nums.sort()
res = []
for i, num in enumerate(nums):
if not res or res[-1][0] != num:
for r in self.permuteUnique(nums[:i] + nums[i+1:]):
res.append([num, *r])
return res