leetcode_gym/_problems/permutations2.md

layout, title, last_solved, category, leetcode_url, status

layout	title	last_solved	category	leetcode_url	status
page	Permutations II	2020-09-24	recursion, backtracking	https://leetcode.com/problems/permutations-ii	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 %}