AlgoScope

Combination Sum

Choose candidates with reuse, in non-decreasing order, until the sum hits the target. Prune the moment a pick would overshoot.

Backtracking, algorithm, intermediate
Pick 2, 5 to go.20316273i
Pick 2, 5 to go.20316273i

Enumeration: Sums to 7 with repeats allowed

Decision, step 2 of 29

7 still needed, a[0] = 2 fits: pick it, {2}, 5 to go. Candidates from index 0 onward stay available, so 2 may repeat.

How enumeration works

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.

Taught by the same lesson

Enumeration covers these too, in the same run.