Reaching a target sum
In combination sum you are given candidate numbers and a target, and must find every multiset of candidates that adds up to the target. In the classic variant each candidate may be reused any number of times.
Recursion with a remaining target
Carry a remaining value that starts at the target and shrinks as you pick numbers:
- If remaining reaches zero, the current path is a valid combination.
- If remaining goes negative, abandon the branch.
- Otherwise loop over candidates from a start index, subtract the chosen value, and recurse.
To allow reuse of a number, recurse with the same index. To avoid duplicate combinations that differ only by order, never move the start index backward; this fixes a non-decreasing order on chosen values.
Pruning with sorting
Sort the candidates first. Then once a candidate exceeds the remaining target, every later candidate does too, so you can break out of the loop immediately. This single break removes large swaths of doomed branches.
Key idea
A shrinking remaining target plus a forward-only start index finds each summing multiset once, and sorting lets you break the loop the instant a candidate overshoots.