Combination Sum (LeetCode 39)
You get an array of distinct positive integers candidates and a target integer target. Find every distinct combination of numbers from candidates that adds up exactly to target, and return them in any order.
A single candidate may be reused as many times as you like within one combination, so two combinations only count as different when they use a different count of at least one number.
Inputs are chosen so that fewer than 150 valid combinations exist for the given candidates and target.
Worked Examples
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]]2+2+2+2, 2+3+3 and 3+5 all make 8; a number may be used more than once.candidates = [2], target = 1[]2s are available, and no number of 2s adds up to 1.⚖️Formal Constraints & Bounds
1 <= candidates.length <= 302 <= candidates[i] <= 40All elements of
candidatesare distinct.1 <= target <= 40
Core Insight
Passing the current index i (not i + 1) back into the recursive call is what allows a candidate to be reused. Branches are cut when a candidate exceeds the remaining target -- a genuine feasibility prune -- and sorting first means the first overshooting candidate proves every later one also overshoots, so the loop can break instead of continue.
Real-World Scenario & Production Applications
Making exact change with unlimited coins of each denomination, or finding every way to combine a fixed set of package sizes to hit an exact shipping weight, both require the same reuse-allowed combination search.
Subproblems & Recurrence Decomposition3 Phases
Sort candidates and iterate from start index. Prune branches early whenever candidates[i] > remain.
for i in range(start, len(candidates)):
if candidates[i] > remain:
break # Prune exceeding candidatesStep-by-Step Execution Trace Table
[ ] (rem=7, start=0, d=0) / \ \ \ choose 2 / choose 3\ choose 6 \ choose 7\ / \ \ \ [ 2 ] (rem=5, d=1)[ 3 ] (rem=4, d=1)[ 6 ] (rem=1, d=1)[ 7 ] (rem=0, d=1) / \ \ | ✅ RECORD [7] choose 2/ choose 3\ choose 3 \ 6>1 ✂️ PRUNE / \ \ [2,2] (rem=3, d=2)[2,3] (rem=2)[3,3] (rem=1) / \ | |choose 2\ choose 3\ 3>2 ✂️ PRUNE 3>1 ✂️ PRUNE [2,2,2] [2,2,3] (d=3) (rem=1) (rem=0) ✅ RECORD [2,2,3] | 2>1 ✂️ PRUNE Step-by-Step Decision Trace
- Step 1 (Root, d=0, rem=7): Candidates:
[2, 3, 6, 7]. - Step 2 (Choose 2, d=1, rem=5):
path = [2]. Pass indexi=0to allow element reuse. - Step 3 (Choose 2, d=2, rem=3):
path = [2, 2]. Pass indexi=0. - Step 4 (Choose 2, d=3, rem=1):
path = [2, 2, 2]. Next candidate2 > 1✂️ PRUNE & BREAK. - Step 5 (Backtrack / Pop 2, d=2):
path = [2, 2],rem = 3. Next candidate:3. - Step 6 (Choose 3, d=3, rem=0):
path = [2, 2, 3].rem == 0Target Hit Record[2, 2, 3]✅. - Step 7 (Backtrack / Pop 3, d=2):
path = [2, 2]. Next candidate6 > 3✂️ PRUNE & BREAK. - Step 8 (Backtrack / Pop 2, d=1):
path = [2],rem = 5. Next candidate:3. - Step 9 (Choose 3, d=2, rem=2):
path = [2, 3]. Next candidate3 > 2✂️ PRUNE & BREAK. - Step 10 (Backtrack to Root, d=0): Next candidate at root is
3. - Step 11 (Choose 3, d=1, rem=4):
path = [3]. Reuse3path = [3, 3](rem=1). Next3 > 1✂️ PRUNE. - Step 12 (Root Candidate 6, d=1):
path = [6](rem=1). Next6 > 1✂️ PRUNE. - Step 13 (Root Candidate 7, d=1):
path = [7](rem=0). Target Hit Record[7]✅. Search Complete: Output[[2, 2, 3], [7]].
candidates = [2,3,6,7], target = 7Expected:[[2,2,3],[7]]| 1 | candidates.sort(), results = [], path = [] |
| 2 | def dfs(start, remaining): |
| 3 | if remaining == 0: |
| 4 | results.append(list(path)) |
| 5 | return |
| 6 | for i in range(start, len(candidates)): |
| 7 | if candidates[i] > remaining: |
| 8 | break |
| 9 | path.append(candidates[i]) |
| 10 | dfs(i, remaining - candidates[i]) |
| 11 | path.pop() |
| 12 | dfs(0, target) |
| 13 | return results |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Every earlier archetype recursed on i + 1, permanently retiring an element once chosen. Here, elements can be reused unlimited times — and the fix is a one-character change with a big conceptual meaning.
The Analogy: An Unlimited Supply of Coin Denominations
Think of this like making change with coins, but with an unlimited supply of every denomination. After choosing to use a $2 coin, you're not forbidden from using another $2 coin next — the coin type stays available for reuse. What does stay forbidden is going back to a $1 coin after you've moved on to considering $2s and larger, since that would just generate the same combination in a different order ([1,2] and [2,1] are the same combination of coins, unlike with permutations).
🔑 The Key Idea in the Code
dfs(i, ...) instead of dfs(i + 1, ...) is the entire trick: the current candidate remains a legal choice for the very next recursive call, while candidates before i are still permanently excluded — giving reuse of the current element without ever re-allowing an earlier, already-passed-over one.
Advancing index
i + 1instead ofi: Because elements can be reused unlimited times, the recursive call must passi(noti + 1) to allow the same element to be chosen again.Exploring candidates when
current_sum + num > target: Sortingcandidatesupfront allows an immediatebreakfrom the loop as soon ascandidates[i] > remaining, pruning entire subtrees.Restarting loop at 0 instead of
start: Starting the candidate loop at 0 generates permutations instead of combinations (e.g.[2, 3]and[3, 2]). Always start loop atstartindex.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Return all combinations summing to target" + explicit unlimited reuse of the same value + distinct candidates.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: remaining is always target minus the sum of path. Complete when remaining == 0. A candidate c is prunable the moment c > remaining, and because candidates are sorted, every later candidate is prunable too.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Passing
i + 1(forbids reuse, becomes Combination Sum II's shape) when the problem explicitly allows reuse -- must passi.Using
continueinstead ofbreakon overshoot -- correct either way, butbreakis the O(N^(T/m))-improving optimisation sorted input licenses, and an interviewer will ask why.Forgetting to sort first -- without it, the overshoot prune cannot safely
break, since a later unsorted candidate might still be small enough.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I sort candidates first, then DFS with (start_index, remaining). If remaining == 0 I record a copy of path. Otherwise I loop from start_index: if candidates[i] > remaining I break, since sorting guarantees every later candidate also overshoots. Otherwise I append it, recurse with (i, remaining - candidates[i]) -- passing i, not i + 1, to allow reuse -- then pop. Time is roughly O(N^(T/m)) where m is the smallest candidate."
Complexity & Mathematical Proof
O(N^(T/M))
Look at the execution steps: Let T = target, M = min(candidates), N = len(candidates). Maximum tree depth is T / M. In the worst case, branching factor is N, giving O(N^(T/M)) operations.
O(T/M) Call Stack
Recursion stack depth <= T / M; path buffer size <= T / M.
T(N, T) = O(N^{T / min(C)})
Derivation Progression
Max Depth = floor(target / min(candidates))
Recursion cannot descend deeper than target divided by smallest coin.
N choices per state
Can reuse current element or move to next candidate index.
if remain < 0: return
Immediately terminates branches exceeding target sum.
Variable Definitions
Number of candidate values
Target remainder sum
Minimum candidate value in the array
Memory Architecture & Bounds
O(T / M) Call stack depth
O(T / M) Current combination path
O(K · D) Result combinations
Boundary Best / Worst Cases
if single candidate equals target.
.
with small candidate values.
Decision & State-Space Search Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "candidates sum to target", "same number chosen unlimited times". Index persistence: when candidate is selected, recurse with index (not ) to allow repeated selection of the same element while preventing duplicate combinations in different orders.
. Sorting candidates upfront enables early loop termination when .
Target exceeds zero: prune immediately if .
Combination Sum (LeetCode 39)
You get an array of distinct positive integers candidates and a target integer target. Find every distinct combination of numbers from candidates that adds up exactly to target, and return them in any order.
A single candidate may be reused as many times as you like within one combination, so two combinations only count as different when they use a different count of at least one number.
Inputs are chosen so that fewer than 150 valid combinations exist for the given candidates and target.
Worked Examples
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]]2+2+2+2, 2+3+3 and 3+5 all make 8; a number may be used more than once.candidates = [2], target = 1[]2s are available, and no number of 2s adds up to 1.⚖️Formal Constraints & Bounds
1 <= candidates.length <= 302 <= candidates[i] <= 40All elements of
candidatesare distinct.1 <= target <= 40
Core Insight
Passing the current index i (not i + 1) back into the recursive call is what allows a candidate to be reused. Branches are cut when a candidate exceeds the remaining target -- a genuine feasibility prune -- and sorting first means the first overshooting candidate proves every later one also overshoots, so the loop can break instead of continue.
Real-World Scenario & Production Applications
Making exact change with unlimited coins of each denomination, or finding every way to combine a fixed set of package sizes to hit an exact shipping weight, both require the same reuse-allowed combination search.
Subproblems & Recurrence Decomposition3 Phases
Sort candidates and iterate from start index. Prune branches early whenever candidates[i] > remain.
for i in range(start, len(candidates)):
if candidates[i] > remain:
break # Prune exceeding candidatesStep-by-Step Execution Trace Table
[ ] (rem=7, start=0, d=0) / \ \ \ choose 2 / choose 3\ choose 6 \ choose 7\ / \ \ \ [ 2 ] (rem=5, d=1)[ 3 ] (rem=4, d=1)[ 6 ] (rem=1, d=1)[ 7 ] (rem=0, d=1) / \ \ | ✅ RECORD [7] choose 2/ choose 3\ choose 3 \ 6>1 ✂️ PRUNE / \ \ [2,2] (rem=3, d=2)[2,3] (rem=2)[3,3] (rem=1) / \ | |choose 2\ choose 3\ 3>2 ✂️ PRUNE 3>1 ✂️ PRUNE [2,2,2] [2,2,3] (d=3) (rem=1) (rem=0) ✅ RECORD [2,2,3] | 2>1 ✂️ PRUNE Step-by-Step Decision Trace
- Step 1 (Root, d=0, rem=7): Candidates:
[2, 3, 6, 7]. - Step 2 (Choose 2, d=1, rem=5):
path = [2]. Pass indexi=0to allow element reuse. - Step 3 (Choose 2, d=2, rem=3):
path = [2, 2]. Pass indexi=0. - Step 4 (Choose 2, d=3, rem=1):
path = [2, 2, 2]. Next candidate2 > 1✂️ PRUNE & BREAK. - Step 5 (Backtrack / Pop 2, d=2):
path = [2, 2],rem = 3. Next candidate:3. - Step 6 (Choose 3, d=3, rem=0):
path = [2, 2, 3].rem == 0Target Hit Record[2, 2, 3]✅. - Step 7 (Backtrack / Pop 3, d=2):
path = [2, 2]. Next candidate6 > 3✂️ PRUNE & BREAK. - Step 8 (Backtrack / Pop 2, d=1):
path = [2],rem = 5. Next candidate:3. - Step 9 (Choose 3, d=2, rem=2):
path = [2, 3]. Next candidate3 > 2✂️ PRUNE & BREAK. - Step 10 (Backtrack to Root, d=0): Next candidate at root is
3. - Step 11 (Choose 3, d=1, rem=4):
path = [3]. Reuse3path = [3, 3](rem=1). Next3 > 1✂️ PRUNE. - Step 12 (Root Candidate 6, d=1):
path = [6](rem=1). Next6 > 1✂️ PRUNE. - Step 13 (Root Candidate 7, d=1):
path = [7](rem=0). Target Hit Record[7]✅. Search Complete: Output[[2, 2, 3], [7]].
candidates = [2,3,6,7], target = 7Expected:[[2,2,3],[7]]| 1 | candidates.sort(), results = [], path = [] |
| 2 | def dfs(start, remaining): |
| 3 | if remaining == 0: |
| 4 | results.append(list(path)) |
| 5 | return |
| 6 | for i in range(start, len(candidates)): |
| 7 | if candidates[i] > remaining: |
| 8 | break |
| 9 | path.append(candidates[i]) |
| 10 | dfs(i, remaining - candidates[i]) |
| 11 | path.pop() |
| 12 | dfs(0, target) |
| 13 | return results |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Every earlier archetype recursed on i + 1, permanently retiring an element once chosen. Here, elements can be reused unlimited times — and the fix is a one-character change with a big conceptual meaning.
The Analogy: An Unlimited Supply of Coin Denominations
Think of this like making change with coins, but with an unlimited supply of every denomination. After choosing to use a $2 coin, you're not forbidden from using another $2 coin next — the coin type stays available for reuse. What does stay forbidden is going back to a $1 coin after you've moved on to considering $2s and larger, since that would just generate the same combination in a different order ([1,2] and [2,1] are the same combination of coins, unlike with permutations).
🔑 The Key Idea in the Code
dfs(i, ...) instead of dfs(i + 1, ...) is the entire trick: the current candidate remains a legal choice for the very next recursive call, while candidates before i are still permanently excluded — giving reuse of the current element without ever re-allowing an earlier, already-passed-over one.
Advancing index
i + 1instead ofi: Because elements can be reused unlimited times, the recursive call must passi(noti + 1) to allow the same element to be chosen again.Exploring candidates when
current_sum + num > target: Sortingcandidatesupfront allows an immediatebreakfrom the loop as soon ascandidates[i] > remaining, pruning entire subtrees.Restarting loop at 0 instead of
start: Starting the candidate loop at 0 generates permutations instead of combinations (e.g.[2, 3]and[3, 2]). Always start loop atstartindex.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Return all combinations summing to target" + explicit unlimited reuse of the same value + distinct candidates.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: remaining is always target minus the sum of path. Complete when remaining == 0. A candidate c is prunable the moment c > remaining, and because candidates are sorted, every later candidate is prunable too.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Passing
i + 1(forbids reuse, becomes Combination Sum II's shape) when the problem explicitly allows reuse -- must passi.Using
continueinstead ofbreakon overshoot -- correct either way, butbreakis the O(N^(T/m))-improving optimisation sorted input licenses, and an interviewer will ask why.Forgetting to sort first -- without it, the overshoot prune cannot safely
break, since a later unsorted candidate might still be small enough.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I sort candidates first, then DFS with (start_index, remaining). If remaining == 0 I record a copy of path. Otherwise I loop from start_index: if candidates[i] > remaining I break, since sorting guarantees every later candidate also overshoots. Otherwise I append it, recurse with (i, remaining - candidates[i]) -- passing i, not i + 1, to allow reuse -- then pop. Time is roughly O(N^(T/m)) where m is the smallest candidate."
Complexity & Mathematical Proof
O(N^(T/M))
Look at the execution steps: Let T = target, M = min(candidates), N = len(candidates). Maximum tree depth is T / M. In the worst case, branching factor is N, giving O(N^(T/M)) operations.
O(T/M) Call Stack
Recursion stack depth <= T / M; path buffer size <= T / M.
T(N, T) = O(N^{T / min(C)})
Derivation Progression
Max Depth = floor(target / min(candidates))
Recursion cannot descend deeper than target divided by smallest coin.
N choices per state
Can reuse current element or move to next candidate index.
if remain < 0: return
Immediately terminates branches exceeding target sum.
Variable Definitions
Number of candidate values
Target remainder sum
Minimum candidate value in the array
Memory Architecture & Bounds
O(T / M) Call stack depth
O(T / M) Current combination path
O(K · D) Result combinations
Boundary Best / Worst Cases
if single candidate equals target.
.
with small candidate values.
Decision & State-Space Search Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "candidates sum to target", "same number chosen unlimited times". Index persistence: when candidate is selected, recurse with index (not ) to allow repeated selection of the same element while preventing duplicate combinations in different orders.
. Sorting candidates upfront enables early loop termination when .
Target exceeds zero: prune immediately if .