Given a collection of distinct integers, return all possible permutations.

Example:


Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Difficulty: interview

Starter code:

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        

Solutions:
class Solution:
     def permute(self, nums):
         """
         :type nums: List[int]
         :rtype: List[List[int]]
         """
         all_permutes = []
         self.permute_nums(all_permutes, nums, [])
         return all_permutes
     
     def permute_nums(self, all_permutes, nums, cur_permute):
         if len(nums) == 0:
             all_permutes.append(cur_permute)
             return
 
         for i in range(len(nums)):
             num = nums[i]
 
             self.permute_nums(all_permutes, nums[0:i] + nums[i+1:len(nums)], cur_permute + [num])

class Solution:
     def permute(self, nums):
         """
         :type nums: List[int]
         :rtype: List[List[int]]
         """
         if not nums:
             return []
 
         nums.sort()
         res = [nums[:]]
         n = len(nums)
         i = n-1
         while i > 0:
             if nums[i-1] < nums[i]:
                 j = n-1
                 while nums[j] < nums[i-1]:
                     j -= 1
                 nums[i-1], nums[j] = nums[j], nums[i-1]
                 nums[i:] = sorted(nums[i:])
                 res.append(nums[:])
                 i = n-1
             else:
                 i -= 1
 
         return res
     
     


class Solution:
 
     def permute(self, nums):
         """
         :type nums: List[int]
         :rtype: List[List[int]]
         """
         
         res = []
         
         self.dfs(nums, [], res)
         
         return res
             
     def dfs(self, nums, path, res):
         if not nums:
             res.append(path)
         
         for i in range(len(nums)):
             self.dfs(nums[:i] + nums[i+1:], path+[nums[i]], res)


class Solution:
     def permute(self, nums):
         """
         :type nums: List[int]
         :rtype: List[List[int]]
         """
         self.res = []
         if not nums or len(nums) == 0:
             return self.res
         self.dfs(0, [], nums)
         return self.res
         
     def dfs(self, i, path, remaining):
         if len(remaining) == 0:
             self.res.append(path)
         for i in range(len(remaining)):
             self.dfs(i+1, path + [remaining[i]], remaining[0:i]+remaining[i+1:])


class Solution:
     def permute(self, nums):
         """
         :type nums: List[int]
         :rtype: List[List[int]]
         """
         res = []
         print(nums)
         
         def swap(a, i, j):
             temp = a[i]
             a[i] = a[j]
             a[j] = temp
         
         def helper(index, path):
             if index == len(nums) - 1:
                 res.append(path.copy())
             for i in range(index, len(nums)):
                 swap(path, index, i)
                 helper(index + 1, path.copy())
             
         helper(0, nums)
         print(nums)
         return res