Medium
Backtracking
Combination Sum
Reuse allowed: recurse on the same index until the remaining target goes negative.
Approach
Backtrack, subtracting a chosen candidate from the target. Since numbers can repeat, recurse with the same start index; move to the next index only when you decide to stop using the current candidate. Prune when the remainder drops below zero.
Time complexity
Exponential (bounded by target/candidates)
Space complexity
O(target) recursion
Common mistake
Advancing the start index after every pick, which forbids reusing a number the problem allows.
See it run, step by step
Generate an interactive lesson for Combination Sum — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Combination Sum