AlgoScope

Permutations

Swap each remaining element into the next position, recurse, and swap back. n! leaves.

Backtracking, algorithm, intermediate
Position 0 takes 1.102132i
Position 0 takes 1.102132i

Enumeration: All orderings of three

Decision, step 2 of 32

Position 0: keep 1 where it is and fix it. Recurse on positions 1 onward.

How enumeration works

Cost

Best
O(n * n!)
Average
O(n * n!)
Worst
O(n * n!)
Space
O(n)

Taught by the same lesson

Enumeration covers these too, in the same run.