Permutations
Backtracking/Permutations
Problem
Given an array nums
of distinct integers, return all the possible permutations. You can return the answer in any order.
Thought Process
We are essentially picking and placing the number in a seperate list and recursing on the new list without that number present
Solution
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
soln = []
self.helper(nums, [], soln)
return soln
def helper(self, nums, permList, soln):
if len(nums) == 0:
soln.append(list(permList))
return
for i in range(len(nums)):
permList.append(nums[i])
remaining = nums[:i] + nums[i+1:]
self.helper(remaining,permList,soln)
permList.pop()
Key Points
In our for-loop, we separate the specific number from the rest of the numbers, append the seperated number to our new list, and recurse on the new seperated list
Time Complexity
Time:
Space:
Last updated
Was this helpful?