[LeetCode] 047. Permutations II
-
date_range April 04, 2019 - Thursday info
Problem (Medium)
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] ]
Approach 1: (My Solution) Backtracking
Idea
- Same idea as the last problem, add another paramter in the backtracking recursion:
index_pool
to differentiate the duplicates. - In the last step, remove duplicate items by
set()
.
Solution
class Solution1:
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
self.backtrack(nums,[], [], res)
res = set([tuple(i) for i in res])
return res
def backtrack(self,nums, index_pool, item, res):
if len(item) == len(nums):
res.append(item)
return
for i in range(len(nums)):
if i in index_pool:
continue
self.backtrack(nums, index_pool + [i], item + [nums[i]], res)
Complexity
- Time: $O()$
- Space: $O()$
Approach 2: Tricky Solution ***
Idea
9-line python solution with 1 line to handle duplication, beat 99% of others :-)
Very similar to Permutation I, see explanations in https://leetcode.com/discuss/19510/my-ac-simple-iterative-java-python-solution. To handle duplication, just avoid inserting a number before any of its duplicates.
Solution
def permuteUnique(self, nums):
ans = [[]]
for n in nums:
new_ans = []
for l in ans:
for i in xrange(len(l)+1):
new_ans.append(l[:i]+[n]+l[i:])
if i<len(l) and l[i]==n: break #handles duplication
ans = new_ans
return ans
Complexity
- Time: $O()$?
- Space: $O()$?
KF