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]
]


Solution

from typing import List

class Solution:
def swap(self, nums: List[int], a, b):
c = nums[a]
nums[a] = nums[b]
nums[b] = c

def permute(self, nums: List[int]) -> List[List[int]]:
permutations = []
self.permuteStep(permutations, nums, 0)
return permutations

def permuteStep(self, permutations: List[List[int]], nums: List[int], index) -> None:
if index == len(nums):
permutations.append(nums.copy())

for i in range(index, len(nums)):
self.swap(nums, index, i)
self.permuteStep(permutations, nums, index + 1)
self.swap(nums, index, i)


Test Cases

test = Solution()
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

[1,2,3,4],
[1,2,4,3],
[1,3,2,4],
[1,3,4,2],
[1,4,2,3],
[1,4,3,2],
[2,1,3,4],
[2,1,4,3],
[2,3,1,4],
[2,3,4,1],
[2,4,1,3],
[2,4,3,1],
[3,1,2,4],
[3,1,4,2],
[3,2,1,4],
[3,2,4,1],
[3,4,1,2],
[3,4,2,1],
[4,1,2,3],
[4,1,3,2],
[4,2,1,3],
[4,2,3,1],
[4,3,1,2],
[4,3,2,1]
]
print('All Passed!')


Big O Analysis

Space Complexity: O(N!)

Time Complexity: O(N!)