154. Generate Permutations

Why this mechanism works

Unlike a subset, a permutation distinguishes different orders. There is no increasing-index restriction: any unused index may fill the next position. The state therefore needs a used flag for every index. Each recursive frame owns one placement and must restore both that flag and the path when it returns.

State and boundaries

path contains distinct chosen input positions in order. used[i] is true exactly when index i appears in path.

Protocol

1. Save path at length n.
2. Scan all indices.
3. Skip used indices.
4. Mark an unused index and append its value.
5. Recurse, then pop and clear its flag.

Visualization

[1,2] -> place 1 -> place 2 -> [1,2]
undo both choices
      -> place 2 -> place 1 -> [2,1]

Python implementation

def permutations(nums):
    output, path = [], []
    used = [False] * len(nums)
    def visit():
        if len(path) == len(nums):
            output.append(path.copy())
            return
        for i, value in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(value)
            visit()
            path.pop()
            used[i] = False
    visit()
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 permutations: output, path = [], []
nums=[1, 2]; output=[]; path=[]

L3 permutations: used = [False] * len(nums)
nums=[1, 2]; output=[]; path=[]; used=[False, False]

L5 visit: if len(path) == len(nums):
nums=[1, 2]; output=[]; path=[]; used=[False, False]

L8 visit: for i, value in enumerate(nums):
nums=[1, 2]; output=[]; path=[]; used=[False, False]; i=0; value=1

L11 visit: used[i] = True
nums=[1, 2]; output=[]; path=[]; used=[True, False]; i=0; value=1

L12 visit: path.append(value)
nums=[1, 2]; output=[]; path=[1]; used=[True, False]; i=0; value=1

L5 visit: if len(path) == len(nums):
nums=[1, 2]; output=[]; path=[1]; used=[True, False]

L8 visit: for i, value in enumerate(nums):
nums=[1, 2]; output=[]; path=[1]; used=[True, False]; i=0; value=1

... 24 intermediate state changes omitted ...

L13 visit: visit()
nums=[1, 2]; output=[[1, 2], [2, 1]]; path=[2]; used=[False, True]; i=1; value=2

L14 visit: path.pop()
nums=[1, 2]; output=[[1, 2], [2, 1]]; path=[]; used=[False, True]; i=1; value=2

L15 visit: used[i] = False
nums=[1, 2]; output=[[1, 2], [2, 1]]; path=[]; used=[False, False]; i=1; value=2

L16 permutations: visit()
nums=[1, 2]; output=[[1, 2], [2, 1]]; path=[]; used=[False, False]

L2 permutations: output, path = [], []
nums=[]; output=[]; path=[]

L3 permutations: used = [False] * len(nums)
nums=[]; output=[]; path=[]; used=[]

L5 visit: if len(path) == len(nums):
nums=[]; output=[]; path=[]; used=[]

L6 visit: output.append(path.copy())
nums=[]; output=[[]]; path=[]; used=[]

L16 permutations: visit()
nums=[]; output=[[]]; path=[]; used=[]

Why the solution is correct

The flags prevent using a position twice, so every leaf is a valid permutation. Any permutation specifies a unique sequence of unused-index choices that the search explores. Restoring both structures preserves the state for sibling branches. Each placement reduces the number of unused indices.

Time and space

O(n*n!) time including copying answers and scanning candidate indices; O(n*n!) output space and O(n) auxiliary state.

Common mistakes

A global visited set that is never cleared turns path-local usage into permanent exclusion. Distinct values are required for uniqueness here.

Reasoning card

Transfer exercise

Use in-place swaps to place each prefix position, and identify exactly which swap must be undone.