Permutations

The search tree is easy to recognize and easy to corrupt. Build one position at a time, choose an unused value, recurse, then undo exactly that choice.

The Contract and the Search Shape

The task is specific:

• nums contains distinct integers.
• Return every arrangement using every value exactly once.
• The output may appear in any order.
• 1 <= len(nums) <= 6.

For [1, 2, 3], the valid results include:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

A permutation is an ordering problem. At the first position, any of the three values can go there. At the second position, two values remain. At the third, one remains:

3 choices × 2 choices × 1 choice = 3! = 6 leaves

That shape tells us the algorithm. We do not need a special rule for each position. At every recursive call, we fill the next open position with any input value that has not been used yet.

This is the core of the permutations backtracking pattern:

1. Choose an unused value.
2. Add it to the partial permutation.
3. Recursively fill the next position.
4. Remove it so the next sibling branch starts clean.

Order matters here. That is why a combinations-style start index is not enough: after choosing 1, we must still be allowed to choose 2 or 3 in different positions.

Choose the State Before the Code

The most common interview mistake is to start writing recursion before deciding what one call means. Define that meaning first.

Let:

• path be the partial permutation currently being built.
• used[i] indicate whether nums[i] already appears in path.
• len(path) be the number of positions already filled.
• result store completed permutations.

The recursive state has a precise interpretation:

At depth k, path contains a valid arrangement for the first k positions, and the next call must fill position k.

For example, while exploring:

path = [1, 3]

the next position must receive the only unused value, 2.

The used array tracks indices rather than values:

nums = [1, 2, 3]
used = [True, False, True]
path = [1, 3]

Index tracking makes the state explicit. It also avoids searching through path to decide whether a candidate has already been selected. With distinct inputs, each index identifies exactly one value.

The base case is equally direct:

if len(path) == len(nums):
    # path is a complete permutation

At that point, the path contains n distinct values drawn from an input of length n. It is a valid answer.

One Python detail carries a large correctness burden: save path[:], not path.

path is one mutable list shared by the entire depth-first search. If you append the same list object to result, later pop() operations will also change the stored answer. A slice creates a snapshot of the current contents.

State contract: path describes the current branch; used describes exactly the values in path; a saved answer must be independent of future mutations.

Derive the Choose–Recurse–Undo Loop

The pseudocode is short because the state does the work:

backtrack():
    if path is complete:
        save a copy of path
        return

    for every input index i:
        if i is already used:
            continue

        choose nums[i]:
            append nums[i] to path
            used[i] = true

        backtrack()

        undo nums[i]:
            remove the last value from path
            used[i] = false

Why can the loop try every input index at every depth? Because any unused value may occupy the next open position. The only restriction is consumption: a value already placed in the current path cannot be placed again.

Consider the first two levels for [1, 2, 3].

At the root:

path = []
unused = {1, 2, 3}

Choose 1:

path = [1]
unused = {2, 3}

From there, choose 2:

path = [1, 2]
unused = {3}

The next call chooses 3:

path = [1, 2, 3]

That path is saved. The recursive call returns, so we undo the last choice:

path = [1, 2]
unused = {3}

The loop at the [1, 2] level has no other candidate. It returns again, and we undo 2:

path = [1]
unused = {2, 3}

Now the sibling branch chooses 3:

path = [1, 3]
unused = {2}

Then 2 completes:

path = [1, 3, 2]

The undo operation is what makes the second branch possible. Without it, the search would remain stuck carrying state from [1, 2, 3].

A useful debugging rule is:

Every mutation before recursion needs a matching inverse mutation after recursion.

If you append without pop(), the path keeps values from completed branches. If you mark an index as used without setting it back to False, later branches lose candidates permanently. The program may still produce some plausible output, which makes this bug more dangerous than a syntax error: the stale state quietly deletes branches.

Prove Complete, Unique Enumeration

Examples show that the code works for one input. The invariant explains why it works for every valid input under the distinct-integer contract.

Invariant

At the start of every backtrack() call:

1. path contains exactly k values, where k = len(path).
2. Those values are distinct input values.
3. used[i] is True exactly when nums[i] appears in path.
4. The next choice must fill position k.

The invariant is true initially: path is empty and every used entry is False.

When the algorithm chooses an unused index i, it appends nums[i] and marks used[i] as True. The path gains one unused value, and the tracking array records that same change. The invariant therefore remains true for the recursive call.

When recursion returns, pop() removes the value and used[i] = False restores the state that existed before the choice. The sibling branch starts from the correct parent state.

Safety

When len(path) == n, the path contains n distinct values selected from an input containing n values. Therefore it contains every input value exactly once. Every saved path is a valid permutation.

Completeness

Take any valid permutation. At depth zero, its first value is one of the available candidates, so the algorithm explores that choice. At the next depth, its second value is still unused, so that choice is available too. The same argument continues through every position.

The branch matching that permutation remains available until it reaches a leaf. Therefore every valid permutation is generated.

Uniqueness

Two different root-to-leaf paths must differ at some first position. The algorithm makes one choice per position, so different choice sequences produce different full arrangements. Because the input values are distinct, the same permutation cannot come from two different index-choice sequences.

This proof depends on the stated contract. If the input contains duplicate values, selecting equal values by different indices can create duplicate output arrangements. That is a different problem contract and requires additional duplicate-handling logic.

Python Implementation

from typing import List


def permute(nums: List[int]) -> List[List[int]]:
    n = len(nums)
    result = []
    path = []
    used = [False] * n

    def backtrack() -> None:
        # Every position has been filled.
        if len(path) == n:
            # Save a snapshot, not the mutable path itself.
            result.append(path[:])
            return

        for i in range(n):
            if used[i]:
                continue

            # Choose nums[i].
            path.append(nums[i])
            used[i] = True

            # Recurse to fill the next position.
            backtrack()

            # Undo exactly what this branch changed.
            path.pop()
            used[i] = False

    backtrack()
    return result

The important lines are deliberately paired:

path.append(nums[i])
used[i] = True

and later:

path.pop()
used[i] = False

That symmetry is more valuable in an interview than a compressed implementation. You can inspect the code and verify that every state change is restored.

The loop scans the original input at each depth. Since output order is unrestricted, there is no reason to sort nums or sort the final result. The input values may be negative or otherwise arbitrary within the problem constraints; their magnitude does not affect the search. Only their distinct identities matter.

Dry Run and Boundary Checks

For [1, 2, 3], the first branch proceeds as follows:

path = []
used = [F, F, F]

choose 1
path = [1]
used = [T, F, F]

choose 2
path = [1, 2]
used = [T, T, F]

choose 3
path = [1, 2, 3]
used = [T, T, T]

The path is complete, so the function copies it into result.

Then the function returns from the deepest call and restores the last choice:

path = [1, 2]
used = [T, T, F]

It returns again and restores 2:

path = [1]
used = [T, F, F]

The next available sibling is 3:

path = [1, 3]
used = [T, F, T]

Now 2 is the only unused value, producing [1, 3, 2].

The restoration is visible in the transition from [1, 2] to [1, 3]. The branch containing 2 has been fully explored, so 2 must be released before 3 can be selected at the same position.

For the minimum permitted input:

permute([7])

the root chooses 7, reaches a path of length one, saves [7], and restores the state. The result contains one permutation.

A practical debugging checklist:

• Is len(path) equal to the number of True entries in used?
• Does the base case save path[:]?
• Does every recursive choice have a pop() afterward?
• Does every used[i] = True have a matching used[i] = False?
• After a recursive call returns, does the parent state look exactly as it did before the choice?
• Are you testing arbitrary values, rather than accidentally relying on sorted or positive input?

Stay within the supplied contract when reasoning about boundaries. The input is nonempty and contains distinct integers. Empty-input and duplicate-input behavior should not be silently promised by this solution.

Complexity Is Set by the Output

For n distinct values, there are exactly:

n!

valid permutations.

The algorithm must materialize all of them, so factorial growth is unavoidable. At each leaf, it copies a path of length n. Therefore the time complexity is:

O(n · n!)

The n! factor comes from the number of answers. The additional n factor comes from copying each complete path into the result.

The auxiliary working space is:

O(n)

That includes:

• path, which holds at most n values;
• used, which holds n booleans;
• the recursion stack, which reaches depth n.

The returned result is separate from auxiliary space. It stores n values for each of n! permutations:

O(n · n!)

This distinction matters in an interview. Saying only “space is O(n!)” hides the cost of storing the values inside each answer. Since the contract requires returning every full arrangement, the output itself dominates memory.

The constraint n <= 6 keeps the required output bounded enough for the problem. The backtracking structure is not wasting factorial work; factorial output is the work.

The Pattern to Reuse

When the answer is a complete ordering, recognize this shape:

1. Identify the next position to fill.
2. Enumerate every candidate not yet consumed.
3. Add one candidate to the partial answer.
4. Recurse.
5. Undo that exact choice.

The reusable object is not a memorized permute() function. It is the state design:

• What does the partial solution contain?
• What choices are legal next?
• How do I know the solution is complete?
• What state must be restored before exploring a sibling?

That state also explains the boundary with combinations. For combinations, order does not matter, so a start index can prevent revisiting earlier choices. For permutations, order changes the answer, so the search must track which values have been consumed while allowing any unused value at the next position.

My interview rule is simple: write the state and restoration symmetry before writing the recursion. If you can say “path is the current partial ordering, used records exactly its members, the leaf saves a snapshot, and the return undoes the choice,” the implementation is nearly mechanical.

Clear the branch. Restore the state. Explore the sibling. That is the permutations solution—and the deeper backtracking habit worth carrying to the next search tree.