Given an array of distinct integers candidates and a target integer, return all unique combinations where the chosen numbers sum to target. The same number may be chosen an unlimited number of times.
candidates = [2,3,6,7], target = 7[[2,2,3],[7]]candidates = [2,3,5], target = 8[[2,2,2,2],[2,3,3],[3,5]]Key difference from Combinations: recurse with i instead of i+1, allowing reuse of the same element. Sorting + break pruning avoids exploring paths that exceed the target. The recursion tree depth is bounded by target/minCandidate.
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.
Pass i, not i plus 1, to allow reuse. Sorting turns "too big" into an early break.
Run the animation above on your own input, or watch the 1:24 video explanation of Combination Sum with a dry run and Java code.