Permutations

There are n factorial (n!) answers — the product n × (n - 1) × ... × 1 — and each answer has length n. That makes O(n · n!) output work unavoidable. Your main design choice is how much temporary data you rebuild along the way.

Recursive insertion

Generate every permutation of the remaining values, then insert the current value into every slot of every smaller permutation. A length-k ordering has k + 1 insertion slots.

def permute(nums: list[int]) -> list[list[int]]:
    def build(index: int) -> list[list[int]]:
        if index == len(nums):
            return [[]]
 
        smaller = build(index + 1)
        answer: list[list[int]] = []
 
        for permutation in smaller:
            for position in range(len(permutation) + 1):
                answer.append(
                    permutation[:position]
                    + [nums[index]]
                    + permutation[position:]
                )
 
        return answer
 
    return build(0)

Every final ordering has one unique position for nums[index]; removing that value recovers exactly one smaller permutation. That proves insertion creates every answer once, but it allocates many intermediate arrays.

Time O(n · n!). Space O(n · n!) for the returned permutations and the largest intermediate batch.

Used-marker backtracking

Backtracking chooses a value, explores below it, then un-chooses it. The choices form a solution-space tree, a tree where depth is the next output position. A marker array records which input positions already appear on the current path. This is the choose/explore/un-choose backtracking pattern applied to positions.

def permute(nums: list[int]) -> list[list[int]]:
    answer: list[list[int]] = []
    path: list[int] = []
    used = [False] * len(nums)
 
    def search() -> None:
        if len(path) == len(nums):
            answer.append(path.copy())
            return
 
        for i, value in enumerate(nums):
            if used[i]:
                continue
 
            used[i] = True
            path.append(value)  # choose
            search()            # explore
            path.pop()          # un-choose
            used[i] = False
 
    search()
    return answer

At depth d, the path contains exactly d distinct input values. Trying every unused value makes every possible next position, and restoring path plus used leaves the next branch a clean state.

Time O(n · n!). Space O(n · n!) for the output, with O(n) auxiliary path, marker, and recursion space. Unlike insertion, this version reuses one partial array throughout the search.