Print all permutations of a given array of integers

permutations.py

"""
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:
Input: nums = [1]
Output: [[1]]
"""
# Approach 1
def permute1(self, nums: List[int]) -> List[List[int]]:
    result = []
    _permute1(nums, 0, len(nums)-1, result)
    return result
    
def _permute1(self, nums: List[int], left: int, right: int, result: List[int]) -> None:
    if left == right:
        result.append(list(nums))
    else:
        for i in range(left, right+1):
            nums[left], nums[i] = nums[i], nums[left]
            _permute1(nums, left+1, right, result)
            nums[left], nums[i] = nums[i], nums[left]

# Approach 2
def permute2(nums: List[int]) -> List[List[int]]:
    result = []
    _permute2(nums, [], result)
    return result

def _permute2(nums: List[int], answer: List[int], result: List[int]) -> None:
	if (len(nums) == 0):
		result.append(answer)
		return
	
	for i in range(len(nums)):
		num = nums[i]
		left = nums[0:i]
		right = nums[i+1:]
		rest = left + right
		_permute2(rest, answer + [num])
      

if __name__ == "__main__":
    nums = [1, 2, 3]
    print(permute1(nums))
    print(permute2(nums))