47. Permutations II

text.md

Permutations II

This is a follow up problem from Permutations. This goal of this problem is to return all possible unique results from the input of an array.

Solution

The solution I followed was Backtracking. Looks like a DFS (Depth-First Search) problem 🤔

Create a hashmap to take count of all number to leave have a non-reapeating digit or eliminate duplicate. Then the bactrack the decision tree.

Code

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result = [] # result
        perm = [] # store permuntation
        count = { i:0 for i in nums } # initilize the count hashmap
        
        # this is to count every number and update the map
        for i in nums:
            count[i] += 1
        
        # create a function to check if the len of the permuation is the same as the input
        def dfs():
            if len(perm) == len(nums):
                result.append(perm.copy())
                return
            
            
            # brute force and go through every number in count
            for j in count:
                if count[j] > 0:
                    perm.append(j)
                    count[j] -= 1
                    
                    dfs()
                    
                    count[j] += 1
                    perm.pop()
                    
        dfs()
        return result

Time Complexity

Well...

This looks like a O(n^2) to me? 😁