Leetcode 46 Permutations

https://leetcode.com/problems/permutations/description

This is problem is asking us to find all possible permutations, one common way to do it is through DFS.

First of all let’s convert this problem into a search tree so it’s easier to reason. e,g [1, 2, 3]

We can abstract the problems this way:

• Each step we choose a number from the given list
• We need to make sure the same number is not picked more than once
• The bottom level are all the results

To make sure the same number is not picked more than once, we can use a set called visited to mark if a number has already been used earlier

Now let’s think about what makes the dfs function:

• What does it do? It should not return anything, just modify the results in place
• How do I break it down to sub problems and call the dfs function again? There will be several possible numbers to add at each step, we can loop through all of them and call the dfs function at each iteration.
• When to stop? When we see the length of the temporary result is equal to the length of nums given, we add the result to the final results and return

Here’s the code

class Solution:
    def dfs(self, nums, results, visited, result):
        if len(result) == len(nums):
            # need to deep copy the result list to a new one
            results.append(result[:])
            return
        
        for num in nums:
            if num in visited:
                continue
            
            visited.add(num)
            result.append(num)
            self.dfs(nums, results, visited, result)
            result.pop()
            visited.remove(num)
            
    
    def permute(self, nums: List[int]) -> List[List[int]]:
        results = []
        visited = set()
        result = []
        self.dfs(nums, results, visited, result)
        
        return results