0

Permutations (Swap and Recurse)

Medium

Fix each candidate in the current position by swapping it forward, recurse on the rest, then swap back.

swap in placefactorial
TimeO(n! * n)
SpaceO(n)
InputUp to 4 values
1
0
2
1
3
2

Decide position 0 first, then position 1, and so on.

1 / 28
dfs(i):
if i == n: record(a); return
for j in i..n-1:
swap(a[i], a[j])
dfs(i+1)
swap(a[i], a[j]) // restore
Why it matters

Swapping avoids a used array and any extra allocation.

Practise this
PermutationsMPermutations IIMNext PermutationMPermutation SequenceH
Keyboard
space play← → stepr restartctrl K search

More in Recursion & Backtracking

N-Queens
Exponential, heavily pruned
Subsets (Take or Skip)
O(n * 2^n)
Sudoku Solver
Exponential in theory, instant in practice
Next visualiser
Sudoku Solver