Combinations
Choose k of n in increasing index order so each combination appears once. Prune when too few remain.
Enumeration: Choose 2 of 4
Take a[0] = 1: chosen is {1}. Candidates from now on start at index 1, so nothing to the left can be picked again.
Cost
- Best
- O(C(n, k) * k)
- Average
- O(C(n, k) * k)
- Worst
- O(C(n, k) * k)
- Space
- O(k)
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Enumeration covers these too, in the same run.