AlgoScope

Combinations

Choose k of n in increasing index order so each combination appears once. Prune when too few remain.

Backtracking, algorithm, intermediate
Take 1 and recurse from index 1.10213243i
Take 1 and recurse from index 1.10213243i

Enumeration: Choose 2 of 4

Decision, step 2 of 24

Take a[0] = 1: chosen is {1}. Candidates from now on start at index 1, so nothing to the left can be picked again.

How enumeration works

Cost

Best
O(C(n, k) * k)
Average
O(C(n, k) * k)
Worst
O(C(n, k) * k)
Space
O(k)

Leads to

Topics that need this one first.

Taught by the same lesson

Enumeration covers these too, in the same run.