BacktrackingRecursion & Backtracking

Permutations

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

Learn Permutations →

Items — Up to 4 distinct numbers, e.g. "1, 2, 3"

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

Complexity

worst O(n · n!)

space O(n)

Speed