Combination Sum
The Prompt
Given an array of distinct integers `candidates` and a target integer `target`, return a list of all unique combinations of `candidates` where the chosen numbers sum to `target`. You may return the combinations in any order. The same number may be chosen from `candidates` an unlimited number of times.
Understanding the Problem
You must list every combination of candidates summing to the target, and any candidate may be reused. That screams decision tree: at each node, choose a candidate to add, subtract it from the remaining target, and recurse. A branch dies when the remainder goes negative and succeeds when it hits exactly zero.
The subtle part is avoiding duplicate combinations like [2, 3, 2] and [2, 2, 3]. The fix is an ordering rule: pass a start index, and only choose candidates at or after it. Reuse is still allowed (you may pick index i again), but you can never go back to an earlier candidate — so each combination is generated exactly once, in non-decreasing candidate order.
The Interview Flow
Interviewer
Given a set of candidate numbers and a target, how do you find all unique combinations that sum to the target, where you can reuse numbers?
Candidate
This is a classic backtracking problem. I need to explore different combinations of numbers. I can think of it as a decision tree.
Interviewer
What decision do you make at each step?
Candidate
At each step in my recursive function, I have to decide which candidate number to add to my current combination. Since I can reuse numbers, if I decide to use `candidates[i]`, my next decision can still be from `candidates[i]` onwards. To avoid duplicate combinations like `[2,2,3]` and `[2,3,2]`, I'll ensure that my next choice of candidate always has an index greater than or equal to the current one.
Interviewer
What are the base cases for your recursion?
Candidate
There are two main base cases. If the current sum equals the target, I have found a valid combination, so I add a copy of it to my results and stop that path. If the current sum exceeds the target, that path is invalid, so I stop and backtrack.
Interviewer
Can you describe the state you need to pass in your recursive function?
Candidate
I'll need the starting index for the candidates to consider (to prevent duplicates), the current combination I'm building, and the current sum. Or, instead of the sum, I could pass the remaining target value, which might be cleaner.
Interviewer
That's a solid backtracking strategy. Please implement it.
Why does backtracking with a start index find each combination exactly once?
The invariant at every tree node: the current path is a non-decreasing sequence of candidates (by index) whose sum plus the remaining target equals the original target. Because every multiset of candidates has exactly one non-decreasing arrangement, each valid combination corresponds to exactly one root-to-leaf path — no duplicates, nothing missed.
Backtracking (pop the last choice after recursion returns) reuses one shared path buffer, so extra space is just O(target / min(candidates)) for the recursion depth. Time is exponential in the worst case — the output itself can be exponential — but pruning on "remaining < 0" cuts every branch the moment it overshoots, which is the practical difference from brute-force enumeration.
Recursive Backtracking Approach
- Initialize a `result` list to store the final combinations.
- Define a recursive `backtrack` function. It should take the current index `i`, the current combination `cur`, and the current sum `total` as arguments.
- **Inside `backtrack(i, cur, total)`:**
- Base Case 1: If `total == target`, a valid combination is found. Add a copy of `cur` to `result` and return.
- Base Case 2: If `i >= len(candidates)` or `total > target`, the path is invalid. Return.
- **Recursive Step (Decision):**
- 1. **Include `candidates[i]`**: Add `candidates[i]` to `cur`. Recursively call `backtrack(i, cur, total + candidates[i])`. We use `i` again because we can reuse the same number.
- 2. **Backtrack**: After the recursive call returns, remove `candidates[i]` from `cur` to explore other possibilities.
- 3. **Don't include `candidates[i]`**: Recursively call `backtrack(i + 1, cur, total)` to explore combinations without the current candidate.
- Start the process by calling `backtrack(0, [], 0)`.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function combinationSum(candidates, target) {
const result = [];
function backtrack(i, cur, total) {
if (total === target) {
result.push([...cur]);
return;
}
if (i >= candidates.length || total > target) {
return;
}
// Include candidates[i]
cur.push(candidates[i]);
backtrack(i, cur, total + candidates[i]);
cur.pop();
// Don't include candidates[i]
backtrack(i + 1, cur, total);
}
backtrack(0, [], 0);
return result;
}Explanation
Search candidates [2, 3, 6, 7] with target 7 — the answer is [[2, 2, 3], [7]].
1Go deep on the smallest candidate: 7 − 2 = 5, 5 − 2 = 3, 3 − 2 = 1. Path so far: [2, 2, 2] with 1 left to make.
2From remain 1 every candidate overshoots (1 − 2 < 0) — prune and backtrack to [2, 2]. Picking 3 gives 3 − 3 = 0: record [2, 2, 3].
3Backtrack to the root and try later candidates. Starting with 3 or 6 never reaches zero (the start index forbids going back to 2), but 7 − 7 = 0: record [7]. Final answer: [[2, 2, 3], [7]].
Complexity Analysis
TIME
O(2^t)
SPACE
O(t)
Finished working through this one?
Mark it complete to track it on your Data Structures path.