105 lines
2.3 KiB
Markdown
105 lines
2.3 KiB
Markdown
---
|
|
layout: page
|
|
title: Permutations II
|
|
last_solved: 2020-09-24
|
|
category: recursion, backtracking
|
|
leetcode_url: https://leetcode.com/problems/permutations-ii
|
|
status: Solved
|
|
---
|
|
|
|
Problem
|
|
-------
|
|
|
|
```
|
|
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]
|
|
]
|
|
|
|
```
|
|
|
|
Solution
|
|
----------
|
|
|
|
This solution works for small cases but TLE on larger cases
|
|
|
|
{% highlight python %}
|
|
|
|
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
|
|
|
|
|
|
output = []
|
|
|
|
def backtrack(currentList):
|
|
|
|
if len(currentList)==len(nums):
|
|
|
|
if sorted(currentList)==sorted(nums) and currentList not in output:
|
|
output.append(currentList.copy())
|
|
|
|
return
|
|
|
|
|
|
for i in range(0, len(nums)):
|
|
|
|
currentList.append(nums[i])
|
|
backtrack(currentList)
|
|
currentList.pop()
|
|
|
|
backtrack([])
|
|
return output
|
|
|
|
|
|
{% endhighlight %}
|
|
|
|
|
|
________________
|
|
|
|
|
|
To combat TLE, I added a visited set to prune the recursion tree.
|
|
|
|
{% highlight python %}
|
|
|
|
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
|
|
|
|
output = []
|
|
visited = set()
|
|
|
|
def backtrack(currentList):
|
|
|
|
# this caches visited nodes so we don't go down duplicated recursion tree paths
|
|
if tuple(currentList) in visited:
|
|
return
|
|
else:
|
|
visited.add(tuple(currentList))
|
|
|
|
|
|
# base case
|
|
if len(currentList)==len(nums):
|
|
|
|
# when these conditions are met, add it to output
|
|
if sorted(currentList)==sorted(nums) and currentList not in output:
|
|
output.append(currentList.copy())
|
|
|
|
return
|
|
|
|
# going down the recursion tree (similar to permutation 1 but without duplicate check)
|
|
for i in range(0, len(nums)):
|
|
|
|
currentList.append(nums[i])
|
|
backtrack(currentList)
|
|
currentList.pop()
|
|
|
|
backtrack([])
|
|
return output
|
|
|
|
{% endhighlight %}
|
|
|
|
 |