Promble
link: https://leetcode.com/problems/permutations-ii/description/
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Approach 1
use itertools libs.
Thought
- def res:Dict to store the final result, keys.
- loop item in permutations(nums)
- use dict key to de-repeat the final result
- res.get(key) vs res[key]: get will return None if key not exist
- res[item] = 0
- return list(res.keys())
Code
from itertools import permutations
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = {}
for item in permutations(nums):
# use dict key to de-repeat
if res.get(item)==None:
res[item] = 0
return list(res.keys())
# return set(list(permutations(nums)))
Approach 2
back track + dfs
Thought
- sort the nums.
- def res:list to store the result.
- def uest:list [False], the index is the nums[i] is used.
- def path:lsit the combintaion list to add in res.
- def dfs(nums, used, path, res)
- if len(path) == len(nums): res.append(path[:]) return # leaf note
- loop i in range(len(nums))
- pruning
- used[i] = True
- self.dfs()
- back track, used[i] = False
- return res
Code
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = []
used = [False] * len(nums)
path = []
nums = sorted(nums)
self.dfs(nums, used, path, res)
return res
def dfs(self, nums, used, path, res):
# leaf nodes
if len(path) == len(nums):
res.append(path[:])
return
# not leaf nodes
for i in range(len(nums)):
if used[i] or (i>0 and nums[i] == nums[i-1] and not used[i-1]):
continue;
used[i] = True
self.dfs(nums, used, path+[nums[i]], res)
# back track
used[i] = False