Combination Sum
Choose candidates with reuse, in non-decreasing order, until the sum hits the target. Prune the moment a pick would overshoot.
Enumeration: Sums to 7 with repeats allowed
7 still needed, a[0] = 2 fits: pick it, {2}, 5 to go. Candidates from index 0 onward stay available, so 2 may repeat.
Cost
- Best
- O(n^(t / min))
- Average
- O(n^(t / min))
- Worst
- O(n^(t / min))
- Space
- O(t / min)
t is the target min the smallest candidate.
Before this
Taught by the same lesson
Enumeration covers these too, in the same run.