Given distinct candidates and a target, return all combinations that sum to the target. The same number may be used any number of times.
DSA Animator › DSA Revision › Backtracking › Combination Sum
Remember: pass i, not i plus 1, to allow reuse. Sorting turns "too big" into an early break. The video solves Combination Sum (LeetCode 39, Medium) with the Backtracking + Reuse pattern from the Backtracking topic, and you can replay every step in the interactive Combination Sum animation.
Given distinct candidates and a target, return all combinations that sum to the target. The same number may be used any number of times.
For candidates 2, 3, 6, 7 and target 7, the answer is 2, 2, 3 and 7.
Trying every multiset of numbers blindly never ends without a limit. The remaining target gives a natural stopping point.
Track the remaining amount, and record the path when it reaches 0. Recurse with the same index i, which allows reusing a number. Sort the candidates, and break as soon as a number is bigger than what remains.
Take 2, 2 and 2, leaving 1, and 2 is too big, so this branch dies. Swap the last 2 for 3, which leaves 0, so record 2, 2, 3. Try 2, 3, leaving 2, then 3 alone and 3, 3, and these all die. 6 leaves 1 and dies, but 7 leaves exactly 0, so record 7. The answer is 2, 2, 3 and 7.
In code, if remaining is 0, add a copy. Loop from start, and break when the candidate exceeds the remaining amount. Choose, recurse with the same i and remaining minus the candidate, then un-choose. The tree depth is at most target over the smallest candidate, so it's exponential in that depth.
Remember: pass i, not i plus 1, to allow reuse. Sorting turns "too big" into an early break.