permutationsV1.py (1156B)
1 # Intuition: 2 3 # Select 1 of n possible options 4 # Remove said option from valid options list 5 # Select next option with same process until len(str) == len(options) 6 7 # Approach: 8 9 # Naive: 10 # Two loops where one specifies an option 11 # and the other loops through the current list of selections 12 # to ensure the current selection is not in there. 13 # This is slow because it loops over each every time. 14 15 # Another approach is similar except 16 # removes the item from a copy of the list each time 17 # while this can be faster, on average it won't be, 18 # and will guarantee the same wctc. 19 20 # Since all nums are unique, I think the first approach is actually the fastest. 21 22 23 class Solution: 24 def permute(self, nums: List[int], current=[]) -> List[List[int]]: 25 26 if len(nums) == 0: 27 return [current] 28 29 results = [] 30 31 for index, num in enumerate(nums): 32 cp_nums = nums.copy() 33 cv = cp_nums.pop(index) 34 cp_current = current.copy() 35 cp_current.append(cv) 36 result = self.permute(cp_nums, cp_current) 37 for res in result: 38 results.append(res) 39 40 return results