LC46 Permutaions

# time O(N*N!) space O(H) H recursion depth
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.size = len(nums)
        self.res = []
        self._backtrack(nums,0)
        return self.res
    def _backtrack(self,arr,start):
        if start == self.size:
            self.res.append(arr[:])
        for i in range(start,self.size):
            arr[start],arr[i] = arr[i], arr[start]
            self._backtrack(arr,start+1)
            arr[start],arr[i] = arr[i], arr[start]

class Solution:
# time O(N*N!) space O(1)
# main idea: insert new number at any possible gap of existing number.
    def permute(self, nums: List[int]) -> List[List[int]]:
        # step0:  initialize res  = [[]]
        size = len(nums)
        res = [[]]
        # edge case: nums is empty 
        if size == 0:
            return res
        
        # step1: loop each number in the nums, at each number crate new res
        for num in nums:
            res_new = []
        #step2: loop each group in res  
            for group in res:
        #step3: in each group, insert num at each position (note +1 to reach right side)
                for i in range(len(group)+1):#  +1 because need to insert at right side which has exceed array right boundry
        #step4: each time perform insertion, append new group into new result 
                    res_new.append(group[:i]+[num]+group[i:])  # insert n 
        #step5 replace old res with updated one 
            res = res_new
        return res