Permutations

Generate every ordering of a list, and see why permutations track used elements instead of a start index

MediumBacktracking· used markers

ArrayBacktrackingRecursion

Problem Statement

Given an array of distinct integers, return all possible permutations — every ordering of all the elements. The answer may be in any order.

Input:  nums = [1, 2, 3]
Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Input:  nums = [0, 1]
Output: [[0,1], [1,0]]

Intuition

There are 3! = 6 permutations of three elements. Where does the factorial come from?

Think about filling three slots. The first slot has 3 candidates. Once one is used, the second slot has 2 left. Then the third has only 1.

3 × 2 × 1 = 6

The key insight

A permutation uses every element exactly once, and the order matters.

So unlike Subsets, nothing is ever skipped — the only question at each slot is which of the still-unused elements goes here.

Why the start-index trick does not work here

In Subsets, a start index prevented duplicates by forcing increasing order. Here that would be fatal.

Subsets:      [1,2] and [2,1] are the SAME     → forbid one, use start
Permutations: [1,2] and [2,1] are DIFFERENT    → keep both, cannot use start

Forcing increasing order would produce only [1,2,3] and lose the other five. Permutations need every element available at every level — minus the ones already placed on this path.

The one thing that changes

	Subsets	Permutations
Candidates at each level	Only those after `start`	Every element not yet used
How duplicates are avoided	Fixed increasing order	Nothing to avoid — order is meaningful
When to record	At every node	Only when the path is full

The decision tree

                  []
        /          |          \
      [1]         [2]         [3]
      / \         / \         / \
  [1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
    |     |     |     |     |     |
 [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]

The tree gets narrower as it deepens — 3 branches, then 2, then 1 — which is exactly the factorial.

Note the answers live only at the leaves. A half-built path like [1, 2] is not a permutation of [1, 2, 3], so nothing is recorded until the path is full.

Approach

Record only when the path is full

When len(path) == len(nums), every element has been placed. Record a copy and return.

Loop over every element, every time

Start at 0, not at a start index. Any unused element is a legal choice for this slot.

Skip elements already on the path

A used boolean array marks which indices are taken on the current path. Skip those.

Choose, explore, undo — including the marker

Mark used, append, recurse, then unmark and pop. Forgetting to unmark is the defining bug of this problem.

Undo both things, or nothing works

used[i] = True
path.append(nums[i])
backtrack()
path.pop()          ← easy to remember
used[i] = False     ← easy to forget

Forget the second line and every element is permanently consumed after its first use. The search then finds exactly one permutation and stops, returning [[1,2,3]].

The symptom is a suspiciously short answer, with no error.

Watch it run

nums = [1, 2, 3] — filling three slots

▲i

path[]used---

Slot 1. All three elements are available. Try index 0 first.

1 / 8

The used markers shrink the candidate pool going down, and restore it coming back up.

Solution

def permute(nums: list[int]) -> list[list[int]]:
    """Return every ordering of a list of distinct integers."""
    results: list[list[int]] = []
    path: list[int] = []
    used = [False] * len(nums)

    def backtrack() -> None:
        # Only a FULL path is a permutation.
        if len(path) == len(nums):
            results.append(path[:])   # copy, not the live array
            return

        for i in range(len(nums)):
            if used[i]:
                continue              # already placed on this path

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

            backtrack()               # explore

            path.pop()                # undo
            used[i] = False           # undo the marker too

    backtrack()
    return results


def permute_swap(nums: list[int]) -> list[list[int]]:
    """Alternative: swap elements into place, avoiding the `used` array."""
    results: list[list[int]] = []

    def backtrack(first: int) -> None:
        if first == len(nums):
            results.append(nums[:])
            return

        for i in range(first, len(nums)):
            nums[first], nums[i] = nums[i], nums[first]   # choose
            backtrack(first + 1)                          # explore
            nums[first], nums[i] = nums[i], nums[first]   # undo the swap

    backtrack(0)
    return results

The swap version, and its one catch

Swapping avoids the used array entirely: everything from first onward is by definition still unplaced.

The catch is that it reorders the input, so the results come out in a different (still complete) order, and the caller's array is temporarily scrambled. It also cannot be adapted to skip duplicates as cleanly, because the swaps destroy any sorting you set up.

Use the used version by default; reach for swapping when memory is tight.

Complexity Analysis

Time Complexity

O(n · n!)

Space Complexity

O(n)

Time — there are n! permutations and copying each costs O(n). The tree has n! leaves, and the internal nodes add lower-order work.
Space — excluding the output: the path, the used array and the recursion stack, each O(n). The output itself is O(n · n!).

Factorials grow terrifyingly fast

`n`	`n!`
5	120
8	40,320
10	3,628,800
12	479,001,600
15	1,307,674,368,000

This is why permutation problems come with n ≤ 8 or so. If a problem allows n = 100, it is not asking you to enumerate orderings — look for a greedy or DP angle instead.

Edge Cases

Subsets — where order does not matter, so a start index applies
Combination Sum — reuse allowed, with pruning
Backtracking — the shared template

Permutations

An empty input, nums = []

A single element

What if the input had duplicates, e.g. [1, 1, 2]?

Why not reuse the start index from Subsets?

On this page