47. Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
Solution: DFS
class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
used = [False] * len(nums)
permutations = []
permutation = []
def dfs():
if len(permutation) == len(nums):
permutations.append(permutation[:])
return
for idx, num in enumerate(nums):
if used[idx]:
continue
if idx > 0 and num == nums[idx - 1] and not used[idx - 1]:
continue
used[idx] = True
permutation.append(num)
dfs()
permutation.pop()
used[idx] = False
dfs()
return permutations
Lessons:
- When a number has the same value as its previous, we can use this number only if its previous is used.