Combination Sum
Choose candidates with reuse, in non-decreasing order, until the sum hits the target; prune the moment a pick would overshoot.
Decision · step 2 of 29Enumeration: 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.
What you will see
Branches die the moment the running sum overshoots.
Cost
| Best | O(n^(t / min)) |
|---|---|
| Average | O(n^(t / min)) |
| Worst | O(n^(t / min)) |
| Space | O(t / min) |
t is the targetmin the smallest candidate.
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Each node of the decision tree announces the choice made and whether it led to success, failure or further choices.
Reduced motion: Tree nodes appear and grey out in place; no travelling focus.
Before this
Taught by the same lesson
Enumeration covers these too, in the same run.