Solutions

# Backtracking + recursion, or recursion building from smaller permutations.
# backtracking

# Backtracking + recursion - O(n * n!) time, O(n! * n) space
def permute(nums: list[int]) -> list[list[int]]:
    res = []
    chosen = [False for _ in range(len(nums))]

    def dfs(cur: list[int], chosen: list[bool]):
        if len(cur) == len(nums):
            res.append(cur)
            return

        for i in range(len(nums)):
            if chosen[i]:
                continue
            
            chosen[i] = True
            dfs(cur + [nums[i]], chosen)
            chosen[i] = False

    dfs([], chosen)
    return res
    

# Recursion building from smaller permutations - O(n * n!) time, O(n! * n) space
def permute(nums: list[int]) -> list[list[int]]:
    if len(nums) == 0:
        return [[]]

    perms = permute(nums[1:])
    res = []
    for p in perms:
        for i in range(len(p) + 1):
            p_copy = p.copy()
            p_copy.insert(i, nums[0])
            res.append(p_copy)
    return res