Description
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]
]
Solutions
1. Backtracking
值得注意的是，这里需要排除一样元素的干扰，可以先排序，然后比较前后两个数是否相同。
# Time: O(n^2)
# Space: O(n)
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
if not nums:
return []
res = []
nums.sort()
self.dfs(nums, [], res)
return res
def dfs(self, nums, path, res):
if not nums or len(nums) == 0:
res.append(path)
n = len(nums)
for i in range(n):
if i >= 1 and nums[i-1] == nums[i]:
continue
self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)
# 30/30 cases passed (48 ms)
# Your runtime beats 98.52 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.8 MB)
2. 迭代方法
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = [[]]
for n in nums:
tmp = []
for item in res:
for i in range(len(item)+1):
tmp.append(item[:i]+[n]+item[i:])
if i < len(item) and item[i] == n:
break
res = tmp
return res
# 30/30 cases passed (48 ms)
# Your runtime beats 98.52 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.9 MB)