Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Find every unique combination of candidates (each reusable unlimited times) that sums to target. The canonical answer is backtracking with a start index: choose a candidate, recurse passing the SAME index `i` (so it can be reused), then un-choose. Passing `i` instead of `i+1` allows reuse; never going backwards (only `i` onward) is what prevents permutation duplicates like [2,3] and [3,2].
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can write a clean backtracking recursion and reason precisely about the two index levers — passing `i` for reuse, and starting at `start` to avoid duplicate combinations — rather than memorising a template.
Where candidates slip
Passing `i + 1` (which forbids reuse and silently fails the problem) or starting the loop at `0` (which produces permutation duplicates like [2,3] and [3,2]). Also forgetting to copy the path before storing it.
How to stand out
State the choose/explore/un-choose template out loud, explain WHY `i` vs `i+1` controls reuse and WHY `start` controls dedup, then add sorting + early `break` pruning and give the O(N^(T/M)) bound.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Each node is a partial path with its remaining target. Branching forward only (start index never decreases) is what prevents [2,3]/[3,2] duplicates. The winning leaves are highlighted.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Generate Subsets, Then Filter
1Hint 1Explore hintHide hint
The literal reading is 'find subsets that sum to target'. How would you enumerate every subset, then keep the ones that hit target?
2Hint 2Explore hintHide hint
A plain subset enumeration uses each element 0 or 1 times — but this problem allows unlimited reuse, so plain subsets can't even represent [2,2,3].
3Hint 3Explore hintHide hint
To allow reuse you'd have to bound a maximum copy count per candidate (target / candidate) and enumerate the cross-product — which is exactly the backtracking tree, but built blindly without pruning.
A · Core idea
The most literal translation is: treat this as a subset-sum problem — enumerate combinations of candidates and keep the ones that add up to target. To honour reuse, you'd cap each candidate at target / candidate copies and enumerate the full cross-product of copy-counts, filtering at the end.
Why this is the natural first thought. The word 'combinations' screams 'subsets', and subset enumeration is a pattern everyone knows. It's worth saying out loud so the interviewer sees you're anchoring on a known technique before refining it.
Why it falls apart. Plain subset enumeration uses each element at most once, so it literally cannot produce [2,2,3] — you'd have to bolt on per-candidate multiplicity bounds, at which point you're enumerating a huge cross-product and only checking the sum at the very end. You explore branches that overshot target long ago, doing exponential work you could have pruned. There's no clean way to stop early. This tells the interviewer 'I know subsets' but also 'I haven't connected the reuse + pruning insight yet'.
The fix it points to. Instead of generating everything and filtering, grow the combination one choice at a time and check the running sum as you go — abandon a branch the instant it overshoots. That incremental, prunable search IS backtracking, and it makes reuse trivial: just allow re-picking the current candidate.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
candidates = [2, 3], target = 4Interactive diagram
Generate-then-filter explores overshoots
boundsCounts of each candidate form a grid; the sum is only checked at the leaves, so overshooting cells (red) are visited and then discarded.
[[2, 2]] — found, but only after checking every pair including overshootsC · Code with teaching comments
Reference implementation preview// Illustrative only — generate bounded multiplicities, filter at the end. public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> results = new ArrayList<>(); enumerate(candidates, 0, target, new ArrayList<>(), results); return results;Explore the full codeHide the full code
D · Why it works and complexityExponential and worse — can't even bound reuse timeO(target / min) recursion depth plus all generated lists spaceOpen the invariant and proofExplore the proofHide the proof
Generate-then-filter separates 'build' from 'check'. Backtracking fuses them: you check the constraint (running sum vs target) at every node and prune dead branches immediately. That fusion is the whole reason the optimal approach is tractable.
ComplexityExponential and worse — can't even bound reuse time, O(target / min) recursion depth plus all generated lists space — Enumerating all bounded-multiplicity combinations without pruning explores branches that have already overshot the target, doing exponential redundant work; you also generate and then discard the vast majority of partial sums.
E · Edge cases and pitfalls4candidates = [2], target = 1 — max_copies = 1 // 2 = 0, so only the empty path is tried; sum 0 ≠ 1 → returns []. Correct but only after a full traversal.Explore edge casesHide edge cases
Edge cases handled
candidates = [2], target = 1max_copies = 1 // 2 = 0, so only the empty path is tried; sum 0 ≠ 1 → returns []. Correct but only after a full traversal.
Pitfalls
- Plain subset enumeration (each element 0/1 times) silently can't represent reuse — you must add multiplicity bounds.
- Checking the sum only at the leaf means overshooting branches are fully explored before being thrown away.
- Forgetting `new ArrayList<>(path)` / `path[:]` stores a reference to the mutating list and corrupts results.
Approach 2 of 2 · Optimal
Backtracking with Start Index (Optimal)
1Hint 1Explore hintHide hint
Instead of generating all subsets and filtering, build one combination incrementally and abandon it the instant the running sum exceeds target. What does each recursion level decide?
2Hint 2Explore hintHide hint
At each level, loop over candidates from a `start` index and 'pick' one: add it to the path, recurse on the reduced target, then remove it (un-choose). Reuse comes from how you recurse.
3Hint 3Explore hintHide hint
To allow reusing the same number, recurse with the SAME index `i` (not `i + 1`). To avoid duplicate combinations like [2,3] and [3,2], make the loop start at `start` so you never go backwards.
A · Core idea
Grow a combination one number at a time. Keep a running remaining = target − (sum of path). At each call, loop i from start to the end: choose candidates[i] (push it), explore by recursing with the new remaining, then un-choose (pop it). When remaining hits 0 we record a copy of the path; when it goes negative we abandon the branch.
Why pass `i` and not `i + 1`. This single character is the whole 'unlimited reuse' rule. Recursing with i means the very next level is still allowed to pick candidates[i] again, so 2 can be chosen as many times as the budget allows ([2,2,2,2]). If you passed i + 1 you'd forbid reuse and you'd be solving Combination Sum II (each element once) instead. Say this trade-off out loud — interviewers love seeing you know exactly which line controls which behaviour.
Why the loop starts at `start`, never at 0. This is the dedup lever. By only ever moving forward (or staying put), we enforce that every combination is generated in non-decreasing index order. So we'll build [2,3] but never [3,2], because once we've moved past index 0 we can't pick 2 again at a later level. That monotonic discipline is precisely what makes the output a set of combinations (multisets) rather than permutations — without it you'd emit [2,3] and [3,2] as separate answers.
Why the un-choose (pop) is non-negotiable. path is a single shared list reused across the entire tree. After exploring the branch where we picked candidates[i], we must pop() it so the next sibling iteration starts from the correct prefix. Skip the pop and the path bleeds choices across branches, producing garbage. And when we hit a solution we append path[:] (a copy) — appending the live list stores a reference that later pops will mutate.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
candidates = [2, 3, 6, 7], target = 7Interactive diagram
Recursion tree for target = 7
start=0, rem=7Each edge is a 'choose'; returning up the tree is an 'un-choose'. Passing i keeps a candidate reusable (the [2,2,3] chain); starting at start blocks backward picks. Winning leaves highlighted, pruned branches in red.
[[2, 2, 3], [7]]C · Code with teaching comments
D · Why it works and complexityO(N^(T/M)) timeO(T/M) spaceOpen the invariant and proofExplore the proofHide the proof
The two index levers are independent knobs: passing `i` vs `i+1` controls reuse (unlimited vs once), and the loop's start position controls ordering (combinations vs permutations). Almost every problem in the subsets/combinations family is just a different setting of these two knobs — internalise them and you stop memorising templates.
ComplexityO(N^(T/M)) time, O(T/M) space — Let M be the smallest candidate. The recursion tree has depth up to T/M (the longest combination), and each node branches up to N ways, giving O(N^(T/M)) nodes; copying a found combination costs O(T/M). Recursion depth (and the path) is O(T/M) extra space, excluding the output.
E · Edge cases and pitfalls5candidates = [2], target = 1 — Sorted, loop picks 2 but 2 > remaining(1) → break immediately, remaining never reaches 0 → returns []. The prune handles it in O(1).Explore edge casesHide edge cases
Edge cases handled
candidates = [2], target = 1Sorted, loop picks 2 but 2 > remaining(1) → break immediately, remaining never reaches 0 → returns []. The prune handles it in O(1).candidates = [2, 3, 5], target = 8Builds [2,2,2,2], [2,3,3], [3,5] in non-decreasing index order; never emits [3,3,2] or [5,3] because the loop only moves forward.
Pitfalls
- Passing `i + 1` instead of `i` — forbids reuse and solves the wrong problem (Combination Sum II).
- Starting the loop at 0 instead of `start` — produces permutation duplicates like [2,3] and [3,2].
- Appending `path` instead of `path[:]` / `new ArrayList<>(path)` — every stored answer ends up mutated to the same final state.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> results = new ArrayList<>(); Arrays.sort(candidates); // enables the early break prune backtrack(candidates, 0, target, new ArrayList<>(), results); return results;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Passing i + 1 (kills reuse)
Recursing with `i + 1` forbids re-picking the current candidate, so [2,2,3] can never form. That's Combination Sum II's rule, not this problem's.
Explore the code comparisonHide the code comparison
Passing i + 1 (kills reuse)
Recursing with `i + 1` forbids re-picking the current candidate, so [2,2,3] can never form. That's Combination Sum II's rule, not this problem's.
Don't write this
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(i + 1, remaining - candidates[i], path) # no reuse!
path.pop()Write this instead
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(i, remaining - candidates[i], path) # reuse allowed
path.pop()2Looping from 0 (permutation duplicates)
Starting at 0 lets later levels pick earlier candidates again, so you emit both [2,3] and [3,2]. Starting at `start` enforces non-decreasing order and dedups.
Explore the code comparisonHide the code comparison
Looping from 0 (permutation duplicates)
Starting at 0 lets later levels pick earlier candidates again, so you emit both [2,3] and [3,2]. Starting at `start` enforces non-decreasing order and dedups.
Don't write this
for i in range(0, len(candidates)): # always from 0
path.append(candidates[i])
backtrack(i, remaining - candidates[i], path)
path.pop()Write this instead
for i in range(start, len(candidates)): # from start
path.append(candidates[i])
backtrack(i, remaining - candidates[i], path)
path.pop()3Storing the live path reference
`results.append(path)` stores the same list object; subsequent pops mutate it, so all results end up identical (often empty). Append a snapshot.
Explore the code comparisonHide the code comparison
Storing the live path reference
`results.append(path)` stores the same list object; subsequent pops mutate it, so all results end up identical (often empty). Append a snapshot.
Don't write this
if remaining == 0:
results.append(path) # reference to a mutating list
returnWrite this instead
if remaining == 0:
results.append(path[:]) # snapshot copy
returnRevise
Carry the pattern into the interview
Pattern to remember
Backtracking with a start index (choose → explore → un-choose)
Code pattern to memorize
def backtrack(start, remaining, path):
if remaining == 0: results.append(path[:]); return
if remaining < 0: return
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(i, remaining - candidates[i], path) # i, not i+1 → reuse
path.pop() # un-chooseRules to remember
- 1Pass
i(noti + 1) into the recursion so the same candidate can be reused unlimited times. - 2The loop starts at
start, never0— that monotonic, never-go-backward rule is what kills permutation duplicates ([2,2,3] but never [2,3,2]). - 3Always
path.pop()after the recursive call — the un-choose step is the discipline that keeps the path correct across sibling branches. - 4Append a copy
path[:]to results, notpathitself — the live list is mutated as you backtrack and would corrupt every stored answer. - 5Prune with
if remaining < 0: return(orbreakif sorted) — never let a dead branch keep recursing.
Use this pattern when
- Asked for **all** combinations / subsets that satisfy a constraint, not just a count
- Elements may be reused unlimited times (or 'how many ways to make X')
- The answer set must be free of permutation duplicates
- Search space is a tree of choices you build incrementally
Choose another pattern when
- Only the **number** of ways is needed, not the combinations → unbounded-knapsack DP is faster
- Each element used at most once and you only need a boolean → subset-sum DP
- Huge candidates with tiny target → DP over target beats exponential backtracking
- Order matters (permutations) → don't use a start index; track a used[] set instead
Interview takeaway
Combination Sum is the canonical 'reuse-allowed' backtracking template. The two levers — pass `i` for reuse and start the loop at `start` for dedup — recur in Combination Sum II, Subsets, Palindrome Partitioning, and Coin Change. Master choose/explore/un-choose here and the whole family falls.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical Backtracking with a Start Index (choose → explore → un-choose). Recognise it whenever you must enumerate ALL combinations/subsets under a constraint. The two levers — pass `i` for reuse, start the loop at `start` for dedup — also drive Combination Sum II, Subsets, Permutations, and Palindrome Partitioning.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Combination Sum IIComing soonEach number used once → pass `i + 1`; candidates have duplicates → sort and skip `candidates[i] == candidates[i-1]` at the same level.
- Combination Sum IIIComing soonUse digits 1–9, each once, exactly k numbers → pass `i + 1` and add a path-length check alongside the sum check.
- Combination Sum IVComing soonOrder matters and only the COUNT is needed → switch to DP over target (unbounded, permutations); backtracking would TLE.
- SubsetsSame start-index template, but record the path at every node instead of only when a sum target is hit.