Problem

Given a set of distinct integers, return all possible permutations.
Example input:
[1, 2, 3]
Example output:
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Solution

# Solution:
# The solution is to use a recursive function that takes in a list of integers and returns a list of lists of integers.
# The function will take the first integer in the list and add it to the beginning of each list in the list of lists returned by the recursive function.
# The recursive function will be called on the list of integers without the first integer.
# The base case is when the list of integers is empty. In this case, the function returns a list containing an empty list.
# The solution is optimal because it is O(n!) time complexity and O(n!) space complexity.

def permute(nums):
    if len(nums) == 0:
        return [[]]
    else:
        first = nums[0]
        rest = permute(nums[1:])
        result = []
        for l in rest:
            for i in range(len(l) + 1):
                result.append(l[:i] + [first] + l[i:])
        return result

print(permute([1, 2, 3]))