TL;DR
Backtrack, filling one position at a time using a used marker (or in-place swaps) — O(n · n!) time, O(n) recursion depth.
Approach 1 — Backtracking with a used array
Grow a partial permutation path. At each level, scan all elements; for any element not yet used, place it, mark it used, recurse, then unmark and remove it. When path holds all n elements, copy it into the result.
from typing import List
def permute(nums: List[int]) -> List[List[int]]:
n = len(nums)
result: List[List[int]] = []
path: List[int] = []
used = [False] * n
def backtrack() -> None:
if len(path) == n:
result.append(path[:])
return
for i in range(n):
if used[i]:
continue
used[i] = True
path.append(nums[i])
backtrack()
path.pop()
used[i] = False
backtrack()
return result
Walkthrough on nums = [1, 2, 3]:
- Place
1 → path [1]. Place 2 → [1,2]. Place 3 → [1,2,3] (length 3, record). Undo to [1,2], no more choices; undo to [1]. Place 3 → [1,3], then 2 → [1,3,2] (record).
- Undo back to
[], place 2 → branch yields [2,1,3] and [2,3,1].
- Undo, place
3 → branch yields [3,1,2] and [3,2,1].
Result: all 6 permutations. The recursion explores this tree, where each leaf is one complete permutation:
flowchart TD
root["[ ]"] --> a1["[1]"]
root --> a2["[2]"]
root --> a3["[3]"]
a1 --> b12["[1,2]"]
a1 --> b13["[1,3]"]
b12 --> c123["[1,2,3]"]
b13 --> c132["[1,3,2]"]
a2 --> b21["[2,1]"]
a2 --> b23["[2,3]"]
b21 --> c213["[2,1,3]"]
b23 --> c231["[2,3,1]"]
a3 --> b31["[3,1]"]
a3 --> b32["[3,2]"]
b31 --> c312["[3,1,2]"]
b32 --> c321["[3,2,1]"]
Complexity: O(n · n!) time — there are n! leaves and copying each completed permutation costs O(n) — and O(n) auxiliary space for path and used (excluding output).
Approach 2 — In-place swapping (no auxiliary used)
Generate permutations by fixing one position at a time inside the array. At index first, swap each candidate nums[i] (for i >= first) into position first, recurse on first + 1, then swap back to restore the array. This drops the separate used array and the growing path; the array itself carries the state.
from typing import List
def permute(nums: List[int]) -> List[List[int]]:
n = len(nums)
result: List[List[int]] = []
def backtrack(first: int) -> None:
if first == n:
result.append(nums[:])
return
for i in range(first, n):
nums[first], nums[i] = nums[i], nums[first]
backtrack(first + 1)
nums[first], nums[i] = nums[i], nums[first]
backtrack(0)
return result
Walkthrough on nums = [1, 2, 3] at first = 0:
i = 0: no-op swap, recurse with [1,2,3] → fixes 1, produces [1,2,3] and [1,3,2].i = 1: swap positions 0 and 1 → [2,1,3], recurse → produces [2,1,3] and [2,3,1], then swap back to [1,2,3].i = 2: swap positions 0 and 2 → [3,2,1], recurse → produces [3,2,1] and [3,1,2], swap back.
Same 6 permutations, generated in a different order (order is unconstrained by the problem).
Complexity: O(n · n!) time, O(n) recursion-stack space — and no extra used/path buffers, so slightly lower constant-factor memory than Approach 1.
Common pitfalls
- Storing
path by reference. result.append(path) keeps a live alias that mutates; use path[:] (or nums[:]) to record a snapshot.
- Forgetting to undo. Skipping
path.pop() / used[i] = False, or the reverse swap, corrupts sibling branches and yields duplicates or missing permutations.
- Swapping back with the wrong indices. In the in-place version, the restore swap must mirror the exact same
first/i pair, or the array drifts out of its original state.
- Assuming duplicates are handled. This problem guarantees distinct inputs; the plain version would emit repeats on duplicate values — that variant (Permutations II) needs an extra sort-and-skip guard.
Pattern takeaway
Permutation generation is the archetype of “choose an item for each position, recurse, undo.” Whether you track availability with a used array or by swapping in place, the invariant is the same: every choice you make must be exactly reversed on the way back up so each branch starts from a clean state.