Backtracking: finding permutations python

PHOTO EMBED

Tue Aug 09 2022 20:11:11 GMT+0000 (Coordinated Universal Time)

Saved by @bryantirawan #python #depth #first #search #recursive #neetcode

class Solution:
    #number of permutations = n! 
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
    
        if len(nums) == 1: 
            return [nums[:]] 
        
        for i in range(len(nums)): 
            #pop off first element 
            n = nums.pop(0)
            
            #numswill now have one less value, will append popped value later 
            perms = self.permute(nums) 
            
            for perm in perms: 
                perm.append(n)
            
            result.extend(perms)
            #adding popped back 
            nums.append(n) 
        
        return result 
 
content_copyCOPY

https://ibb.co/syS9tgW: basic decision tree to find permutations https://ibb.co/Xz5BKqD: actual decision tree. We are removing first element in array until we get to sub permutation length 1 (base case) then append all the popped variables back

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