Permutations

Given n distinct integers, list all n! orderings — grow one prefix at a time, trying every still-unused number in the next slot and undoing each choice on the way back.

The memory hook

Fix one slot at a time, try every unused number in it, then un-choose and try the next.

MediumBacktracking + used setO(n · n!) timeO(n) space

One slot, every candidate, then undo

intuition

A permutation is built left to right: at every moment only the next empty slot is a decision, and its candidates are exactly the numbers not already placed. The recursion goes deep on the first candidate before the loop ever advances — that depth-first order is what enumerates every ordering without repetition.

1Grow one prefixThe current path holds slots 0..k−1, already fixed. Position k is the only decision this frame makes; everything after k stays empty.

2Skip what is usedA boolean array marks the numbers already in the prefix. The loop tries only unmarked indices, so no branch ever reuses a number or repeats a sibling's prefix.

3Undo on the way backAfter the recursive call returns, pop the path and clear the mark. The state is bit-for-bit what the loop started with, so the next candidate begins clean.

The one sentence to remember: After finishing position k, the path holds one exact prefix and the marks name precisely its members — that pairing is the whole invariant.

Watch the prefix grow and shrink

playable trace

Step through [1, 2, 3]. Each frame fixes one slot or undoes it; the six lime frames are the moments the path reaches full length and a copy is recorded.

Playable trace · backtracking + used set

Frames are generated from the same logic as the code below.

Presets

Current event

Ready — press Play

Found

0 / 6

Completions

The path starts empty and nothing is marked used. Press Play.

unused current choice in path just undone complete

0 / 0 speed 650ms

Choose, recurse, un-choose

the solution

Python · backtracking + used set

class Solution:
    def permute(self, nums):
        res = []
        used = [False] * len(nums)
        def dfs(path):
            if len(path) == len(nums):  # full length: one complete order
                res.append(path[:])  # copy: path keeps mutating
                return
            for i, x in enumerate(nums):  # every candidate for this slot
                if used[i]:
                    continue
                used[i] = True
                path.append(x)
                dfs(path)
                path.pop()  # undo: free the slot for the next candidate
                used[i] = False
        dfs([])
        return res

The displayed Python and the trace above use the same logic: full-length copy, skip-used loop, and paired undo. (An in-place swap variant exists; this used-array form makes the invariant visible.)

Complete at full lengthif len(path) == len(nums)The only place answers are recorded. Nothing shorter is ever emitted, and every full-length path is copied exactly once.

Skip usedif used[i]: continueEach level tries each value at most once and never reuses a prefix member — that is why branches are distinct with no dedup pass.

Undo both halvespath.pop(); used[i] = FalseBoth halves of the choice revert together. Forgetting either leaks state into every later sibling of the loop.

Why is every ordering listed exactly once? Induction on the prefix: position k tries each still-unused value once, and the recursive call enumerates all completions of that prefix. Disjoint candidates give disjoint subtrees, and together they cover all n! orders.

TimeO(n · n!)n! full-length leaves, each copied at cost n; internal nodes are bounded by e · n! and cost O(1) amortized per edge.

SpaceO(n)path + used + recursion depth n besides the output, which itself holds n! × n integers.

Two quick mental checks

make it stick

nums = [1,2,3]

→ 6 permutations

Fixing 1 first yields [1,2,3] then [1,3,2] before 2 ever takes slot 0 — depth-first, not breadth. The trace's first two lime frames are exactly that pair.

nums = [0,1]

→ [[0,1],[1,0]]

The smallest non-trivial case: two candidates for slot 0, one forced pick each after. Edge [1] returns [[1]] — the loop runs once and the full-length test fires immediately.

What to say out loud

I depth-first search over prefixes: at each level I try every unused number in the next slot, mark it used, recurse, then pop and unmark so siblings start clean. When the path reaches full length I copy it — that copy is one permutation, and the loop order yields all n factorial exactly once.