Permutations

Signal

"Every possible ordering" is choose-explore-unchoose again, but unlike subsets, order matters and every element must appear in every result — so track which elements are already placed rather than shrinking a start index.

Approach

Backtrack by picking, at each position, any not-yet-used element: mark it used, append it to the path, recurse to fill the next position, then remove it and mark it unused again before trying the next candidate. A path is complete — and recorded — once it holds every element.

Skeleton

def backtrack(path, used):
    if len(path) == len(nums): results.append(copy of path); return
    for i, x in enumerate(nums):
        if used[i]: continue
        used[i] = True; path.append(x)
        backtrack(path, used)
        path.pop(); used[i] = False

Solution

def permute(nums: list[int]) -> list[list[int]]:
    results: list[list[int]] = []
    path: list[int] = []
    used = [False] * len(nums)

    def backtrack() -> None:
        if len(path) == len(nums):
            results.append(path[:])
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(x)
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return results

Complexity

O(n! · n) time — there are n! permutations, and building/copying each costs O(n). O(n) auxiliary space for used and the recursion depth.

Pitfalls

• Using a start index like subsets/combination-sum instead of a used array — every element must be available at every position here, not a shrinking suffix.
• Forgetting to reset used[i] = False after popping — a leftover "used" flag from a finished branch silently excludes that element from sibling branches.
• Inputs with duplicate values (a common follow-up) make this exact solution emit duplicate permutations — that needs sorting first plus a "skip if this value was already tried at this position" guard.