BacktrackingAlgorithmaka all orderings, arrangements, n!

Permutations

Enumerate all n! orderings of a sequence by choosing an unused element for each position in turn.

▶ VisualizePattern: BacktrackingPractice (2)
Progress

Overview

A permutation is an ordering of all n elements; there are n! of them. Backtracking fills positions 0, 1, …, n−1 in order, and at each position tries every element not yet used. The used boolean array (or a bitmask) is the state that distinguishes permutations from Subsets (Power Set): order matters, so a chosen element must be excluded from later positions rather than "everything before it".

An in-place alternative swaps a[pos] with each a[i] for i ≥ pos, recurses, and swaps back. It needs no extra array but produces permutations in non-lexicographic order and complicates duplicate handling.

backtrackingn!used arrayswap methodordering

Intuition

A mental model before the formal terms.

Think of n numbered balls and n empty slots in a row. Fill slot 1 with any ball (n ways), slot 2 with any remaining ball (n−1 ways), and so on. The recursion tree has n children at the root, n−1 at the next level, … — n! leaves in total.

Un-choose is putting the ball back in the bag so the next branch can pick it for the same slot.

How it works

  1. Maintain path (the partial ordering) and used[i] for each index.
  2. Base case: len(path) == n — record a copy.
  3. For each i in 0..n-1 with used[i] == false: mark used, push a[i], recurse, pop, unmark.
  4. For inputs with duplicates, sort first and skip i if a[i] == a[i-1] and used[i-1] is false: among equal values, only allow choosing them left to right.

Why it works

Every permutation is a sequence of distinct indices; the used array ensures distinctness while the position-by-position loop ensures every sequence is reachable. Each permutation corresponds to exactly one root-to-leaf path.

The duplicate rule works because it fixes a canonical order among equal elements: the copies of a value appear in the permutation in the same relative order as in the sorted input, so each distinct permutation is generated exactly once.

Recognition

How to tell a problem wants this.

  • "Return all permutations / arrangements / orderings" with n ≤ 10 (10! ≈ 3.6·10^6).
  • Search over orderings of tasks, cities, or letters where any prefix can be checked for validity (pruning).
  • Constraints like n ≤ 8 in a puzzle strongly suggest brute-forcing all orderings.
“all combinations” → Backtracking

Interactive visualization

Play, step, change the input. ← → and space work too.

Call stack (top first)
empty
used[]
1: no2: no3: no
Permutations (0)
empty
1/53Generate all 3! permutations of [1, 2, 3] by filling slots left to right and trying every unused element in each slot.
Call on the stackCall returnedJust placedAlready used
PseudocodeLearn Permutations →
1go(current, used):
2  if len(current) == n: record(current); return
3  for i in 0 .. n-1:
4    if used[i]: continue
5    used[i] = true; current.push(a[i])
6    go(current, used)
7    current.pop(); used[i] = false      // backtrack
Variables
n3
Complexity
worst O(n · n!)
space O(n)
Speed

Pseudocode

1sort(a)  # only for duplicates
2backtrack(path, used):
3  if len(path) == n: record(copy of path); return
4  for i in 0..n-1:
5    if used[i]: continue
6    if i > 0 and a[i] == a[i-1] and not used[i-1]: continue
7    used[i] = true; path.push(a[i])
8    backtrack(path, used)
9    path.pop(); used[i] = false

Implementations

1def permutations(nums: list[int]) -> list[list[int]]:
21 · Sort and allocate used[]
3    nums = sorted(nums)
4    n = len(nums)
5    used = [False] * n
6    out: list[list[int]] = []
7    path: list[int] = []
8 
9    def backtrack() -> None:
102 · Base case: full permutation
11        if len(path) == n:
12            out.append(path[:])
13            return
14        for i in range(n):
153 · Skip used and duplicate branches
16            if used[i]:
17                continue
18            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
19                continue         # equal values must be taken left to right
204 · Choose / explore / un-choose
21            used[i] = True
22            path.append(nums[i])
23            backtrack()
24            path.pop()
25            used[i] = False
26 
27    backtrack()
28    return out
Walkthrough
  1. used = [False] * n builds the marker list; list multiplication is fine for immutable booleans.
  2. out.append(path[:]) stores a copy when the path is complete.
  3. nums[i] == nums[i - 1] and not used[i - 1] enforces left-to-right use of equal values so each distinct permutation appears once.
  4. Both path.pop() and used[i] = False restore state after recursion.
Complexity (this implementation)
time O(n * n!) · space O(n) recursion depth plus O(n * n!) output

Python call overhead makes this noticeably slower than itertools.permutations, which is implemented in C.

Language notes
  • itertools.permutations(nums) yields tuples lazily in lexicographic order of positions; it does not dedupe equal values (wrap in set if needed).
  • used could be a bytearray(n) for a small speed win.
  • Recursion depth equals n, well below the default limit.
Common mistakes in this language
  • Appending path instead of path[:].
  • Forgetting to sort first when handling duplicates.
  • Using itertools.permutations and expecting deduplicated output for inputs with repeats.
Language differences that matter here
  • C++ (std::next_permutation) and Python (itertools.permutations) have stdlib generators; JS/TS do not, so the recursive version is what you ship.
  • Only std::next_permutation dedupes equal values automatically; itertools.permutations does not.
  • JS/TS need a numeric comparator for the sort that the duplicate rule depends on.

Complexity

Best
—
Average
—
Worst
O(n · n!)
Space
O(n)

n! leaves, each copied in O(n); internal nodes add a factor bounded by e ≈ 2.7. Recursion depth n plus the used array.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • All orderings are required, or the search over orderings can be pruned early by a prefix check.
  • n ≤ 10. For n ≤ ~18 with a cost function over orderings, prefer Bitmask DP (O(2^n · n^2)) over n!.
Avoid it when
  • You need the next permutation in lexicographic order, not all of them — that is an O(n) in-place algorithm.
  • Only the count is needed: n! or a multinomial coefficient from Combinatorics.
  • Optimal ordering with additive cost (TSP-like) for n up to 16–20: Bitmask DP beats enumeration.

Alternatives

Bitmask DPCombinatoricsSubsets (Power Set)

Common mistakes

  • Duplicate skip with used[i-1] true instead of false — both conventions can work, but mixing them produces duplicates or misses.
  • Using the swap method with duplicates and expecting unique output.
  • Forgetting to reset used[i] after the recursive call.
  • Recording path without copying.

Interview patterns

  • Permutations II (duplicates) via sort + skip.
  • Letter case permutation and phone-number letter combinations: per-position choice sets.
  • Beautiful arrangement / N-th permutation: prune with a per-position constraint or compute directly with factorial number system.
Interview questions on this
Mock interviews

Example problems

N-QueenshardPermutationsmedium