permutations.py

defpermute_recursive(nums: list[int]) ->list[list[int]]:
"""
 Return all permutations.

 >>> permute_recursive([1, 2, 3])
 [[3, 2, 1], [2, 3, 1], [1, 3, 2], [3, 1, 2], [2, 1, 3], [1, 2, 3]]
 """
result: list[list[int]] = []
iflen(nums) ==0:
return [[]]
for_inrange(len(nums)):
n=nums.pop(0)
permutations=permute_recursive(nums.copy())
forperminpermutations:
perm.append(n)
result.extend(permutations)
nums.append(n)
returnresult


defpermute_backtrack(nums: list[int]) ->list[list[int]]:
"""
 Return all permutations of the given list.

 >>> permute_backtrack([1, 2, 3])
 [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
 """

defbacktrack(start: int) ->None:
ifstart==len(nums) -1:
output.append(nums[:])
else:
foriinrange(start, len(nums)):
nums[start], nums[i] =nums[i], nums[start]
backtrack(start+1)
nums[start], nums[i] =nums[i], nums[start] # backtrack

output: list[list[int]] = []
backtrack(0)
returnoutput


if__name__=="__main__":
importdoctest

result=permute_backtrack([1, 2, 3])
print(result)
doctest.testmod()