← Back to DSA Animator
Combination Sum LC #39 Medium Backtracking · Reuse · Pruning
Problem

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.

Example 1
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation: 2+2+3=7 and 7=7.
Example 2
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Explanation: Three ways to reach 8.
Constraints: 1 ≤ candidates.length ≤ 30  |  2 ≤ candidates[i] ≤ 40  |  All distinct  |  1 ≤ target ≤ 40
Try Examples
Custom:
Approach
Backtracking — Recurse with i (Reuse)
Key difference: recurse with i (not i+1) to allow reuse. rem tracks remaining sum. Sort + break when c[i]>rem avoids exceeding target.
Candidates (sorted)
Current Path
curr = [ ] (empty)
Remaining (rem)
—
Results 0 found
Variables
curr sum
0
rem
—
start
0
found
0
Step Logic
Press ▶ Play or Next Step to begin.
✅
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Candidates can be reused → recurse with i (not i+1)
2
rem tracks remaining sum; base case rem==0 → found combination
3
Pruning: if c[i]>rem → break (sorted, all further candidates also larger)
4
Sort enables early break pruning
Time
O(n^(t/m))
Space
O(t/m)
Why Backtracking Works

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.