Combination Sum (LeetCode
Learn how to solve Combination Sum using backtracking, recursion, candidate reuse, sorting, and pruning. Includes intuition, decision trees, dry runs, Java code, complexity analysis, duplicate handling, interview tips, and production applications.
Introduction
Combination Sum is one of the most important backtracking interview problems.
It extends the concepts learned from:
- Subsets
- Permutations
- Combinations
The important difference is that each candidate may be selected multiple times.
This problem is frequently discussed in interviews at companies such as:
- Amazon
- Microsoft
- Meta
- Apple
- Adobe
- Bloomberg
- Goldman Sachs
- JPMorgan Chase
It evaluates your understanding of:
- Backtracking
- Candidate reuse
- Target-based recursion
- Search-space pruning
- Duplicate prevention
- Sorting
- Recursive state management
- Exponential complexity
The central idea is:
Choose a candidate, reduce the remaining target, recursively continue from the same candidate index, and undo the choice before exploring another branch.
Problem Statement
Given an array of distinct positive integers called candidates and a positive integer target, return all unique combinations where the selected numbers add up to target.
A candidate may be selected an unlimited number of times.
The combinations may be returned in any order.
Example 1
Input
candidates = [2,3,6,7]
target = 7
Output
[
[2,2,3],
[7]
]
Explanation:
2 + 2 + 3 = 7
7 = 7
The candidate 2 may be reused.
Example 2
Input
candidates = [2,3,5]
target = 8
Output
[
[2,2,2,2],
[2,3,3],
[3,5]
]
Example 3
Input
candidates = [2]
target = 1
Output
[]
No valid combination exists.
What Makes Combination Sum Different?
The problem combines several important rules:
- Every result must sum to the target.
- A candidate may be reused.
- Order does not matter.
- Duplicate combinations must not be returned.
For example:
[2,2,3]
and:
[3,2,2]
represent the same combination.
Only one should be returned.
Combination Sum vs Combinations
| Combinations | Combination Sum |
|---|---|
Select exactly k elements |
Select elements that reach a target |
| Each input value usually used once | Candidate reuse is allowed |
Base condition is size k |
Base condition is remaining target 0 |
Recurse with i + 1 |
Recurse with i |
| Fixed result length | Variable result length |
Combination Sum vs Subsets
| Subsets | Combination Sum |
|---|---|
| Every subset is valid | Only target-sum paths are valid |
| Each element used once | Elements may be reused |
| Save every recursion state | Save only when target becomes zero |
| Usually no pruning for positive values | Strong pruning based on remaining target |
Core Backtracking State
The recursive state includes:
start— candidate index from which choices are allowedremaining— target amount still requiredcurrent— combination being builtresult— completed combinations
At every recursive call:
Current Combination
Remaining Target
Next Candidate Index
Choose–Explore–Unchoose
Choose
Add the current candidate.
current.add(candidates[i]);
Explore
Reduce the remaining target and recurse.
backtrack(
candidates,
i,
remaining - candidates[i],
current,
result);
Notice the recursive call uses:
i
not:
i + 1
This allows the same candidate to be reused.
Unchoose
Remove the last candidate.
current.remove(
current.size() - 1);
This restores the previous state.
Base Conditions
Valid Combination
When:
remaining == 0
the current combination reaches the target.
Save a copy.
result.add(
new ArrayList<>(current));
Invalid Branch
When:
remaining < 0
the selected values exceed the target.
Stop exploring the branch.
If candidates are sorted, branches can be pruned before recursion when the next candidate is greater than the remaining target.
Decision Tree Intuition
For:
candidates = [2,3,6,7]
target = 7
A simplified decision tree is:
graph TD
remaining_0_0["remaining"] --> N_2_1_1["2"]
remaining_0_0["remaining"] --> N_3_1_2["3"]
N_7_0_1["7"] --> N_6_1_3["6"]
N_7_0_1["7"] --> N_7_1_4["7"]
N_2_1_1["2"] --> N_2_2_1["2"]
N_2_1_1["2"] --> N_3_2_2["3"]
N_3_1_2["3"] --> N_6_2_3["6"]
N_3_1_2["3"] --> N_7_2_4["7"]
N_2_2_1["2"] --> remaining_3_1["remaining"]
N_2_2_1["2"] --> N_5_3_2["5"]
N_3_2_2["3"] --> remaining_3_3["remaining"]
N_3_2_2["3"] --> N_4_3_4["4"]
N_6_2_3["6"] --> remaining_3_5["remaining"]
N_6_2_3["6"] --> N_1_3_6["1"]
N_7_2_4["7"] --> remaining_3_7["remaining"]
N_7_2_4["7"] --> N_0_3_8["0"]
remaining_3_1["remaining"] --> N_2_4_1["2"]
remaining_3_1["remaining"] --> N_3_4_2["3"]
N_5_3_2["5"] --> N_3_4_3["3"]
N_5_3_2["5"] --> N_6_4_4["6"]
remaining_3_3["remaining"] --> stop_4_5["stop"]
remaining_3_3["remaining"] --> save_4_6["save"]
N_2_4_1["2"] --> N_2_5_1["2"]
N_2_4_1["2"] --> N_2_5_2["2"]
N_3_4_2["3"] --> N_2_5_3["2"]
N_3_4_2["3"] --> N_3_5_4["3"]
N_3_4_3["3"] --> N_3_5_5["3"]
N_3_4_3["3"] --> N_3_5_6["3"]
N_2_5_1["2"] --> rem_6_1["rem"]
N_2_5_1["2"] --> N_3_6_2["3"]
N_2_5_2["2"] --> rem_6_3["rem"]
N_2_5_2["2"] --> N_2_6_4["2"]
N_2_5_3["2"] --> rem_6_5["rem"]
N_2_5_3["2"] --> N_1_6_6["1"]
rem_6_1["rem"] --> N_2_7_1["2"]
rem_6_1["rem"] --> N_3_7_2["3"]
N_2_7_1["2"] --> N_2_8_1["2"]
N_2_7_1["2"] --> N_2_8_2["2"]
N_3_7_2["3"] --> N_2_8_3["2"]
N_2_8_1["2"] --> rem_9_1["rem"]
N_2_8_1["2"] --> N_1_9_2["1"]
rem_9_1["rem"] --> N_2_10_1["2"]
rem_9_1["rem"] --> N_2_10_2["2"]
N_1_9_2["1"] --> N_3_10_3["3"]
N_2_10_1["2"] --> rem_11_1["rem"]
N_2_10_1["2"] --> N_0_11_2["0"]
rem_11_1["rem"] --> save_12_1["save"]
Valid leaves:
[2,2,3]
[7]
Approach 1 — Basic Backtracking
Core Idea
Try every candidate starting from the current index.
The same index is passed recursively so the current candidate can be reused.
Java Code — Basic Backtracking
import java.util.ArrayList;
import java.util.List;
public class CombinationSum {
public List<List<Integer>> combinationSum(
int[] candidates,
int target) {
List<List<Integer>> result =
new ArrayList<>();
backtrack(
candidates,
0,
target,
new ArrayList<>(),
result);
return result;
}
private void backtrack(
int[] candidates,
int start,
int remaining,
List<Integer> current,
List<List<Integer>> result) {
if (remaining == 0) {
result.add(
new ArrayList<>(current));
return;
}
if (remaining < 0) {
return;
}
for (int i = start;
i < candidates.length;
i++) {
current.add(
candidates[i]);
backtrack(
candidates,
i,
remaining - candidates[i],
current,
result);
current.remove(
current.size() - 1);
}
}
}
Why Use a Start Index?
Without a start index, the algorithm may generate reordered duplicates.
Example:
[2,2,3]
[2,3,2]
[3,2,2]
All represent the same combination.
Using start ensures candidates are selected in non-decreasing index order.
The algorithm generates only:
[2,2,3]
Why Recurse with i Instead of i + 1?
Because candidates may be reused.
Suppose the selected candidate is:
2
The combination:
[2,2,3]
requires selecting 2 again.
Therefore:
backtrack(
candidates,
i,
remaining - candidates[i],
current,
result);
If the recursion used i + 1, each candidate could be selected only once.
That would solve a different problem.
Detailed Dry Run
Input:
candidates = [2,3,6,7]
target = 7
Initial state:
start = 0
remaining = 7
current = []
Choose 2
current = [2]
remaining = 5
Recurse from index 0.
Choose 2 Again
current = [2,2]
remaining = 3
Recurse from index 0.
Choose 2 Again
current = [2,2,2]
remaining = 1
Choose 2 again:
remaining = -1
Invalid branch.
Backtrack to:
current = [2,2]
Choose 3
current = [2,2,3]
remaining = 0
Valid combination.
Save:
[2,2,3]
Backtrack.
Choose 3 After One 2
current = [2,3]
remaining = 2
Trying 3, 6, or 7 exceeds the target.
No valid combination.
Choose 3 at Root
current = [3]
remaining = 4
Possible attempts:
[3,3]
remaining = 1
No candidate can complete the target.
Choose 6 at Root
current = [6]
remaining = 1
No valid continuation.
Choose 7 at Root
current = [7]
remaining = 0
Save:
[7]
Final Result
[
[2,2,3],
[7]
]
Dry Run Table
| Current | Remaining | Next Choice | Action |
|---|---|---|---|
[] |
7 | 2 | Choose |
[2] |
5 | 2 | Choose |
[2,2] |
3 | 2 | Choose |
[2,2,2] |
1 | 2 | Exceeds target |
[2,2] |
3 | 3 | Save [2,2,3] |
[2] |
5 | 3 | Explore |
[] |
7 | 3 | Explore |
[] |
7 | 6 | Explore |
[] |
7 | 7 | Save [7] |
Approach 2 — Sorting and Pruning
Core Idea
Sort the candidates first.
When:
candidate > remaining
the candidate cannot be selected.
Because the array is sorted, every candidate after it is also too large.
The loop can stop immediately.
Java Code — Optimized Backtracking
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class CombinationSumOptimized {
public List<List<Integer>> combinationSum(
int[] candidates,
int target) {
if (candidates == null) {
throw new IllegalArgumentException(
"Candidates must not be null");
}
if (target < 0) {
throw new IllegalArgumentException(
"Target must not be negative");
}
Arrays.sort(candidates);
List<List<Integer>> result =
new ArrayList<>();
backtrack(
candidates,
0,
target,
new ArrayList<>(),
result);
return result;
}
private void backtrack(
int[] candidates,
int start,
int remaining,
List<Integer> current,
List<List<Integer>> result) {
if (remaining == 0) {
result.add(
new ArrayList<>(current));
return;
}
for (int i = start;
i < candidates.length;
i++) {
int candidate =
candidates[i];
if (candidate > remaining) {
break;
}
current.add(candidate);
backtrack(
candidates,
i,
remaining - candidate,
current,
result);
current.remove(
current.size() - 1);
}
}
}
Why Sorting Improves Pruning
Suppose:
remaining = 4
candidates = [2,3,6,7]
When the loop reaches:
6
we know:
6 > 4
Because later candidates are 7 or greater, none can fit.
The loop stops.
Without sorting, the algorithm would need to continue checking every remaining candidate.
Input Validation
The classic problem assumes all candidates are positive.
This is important because reusable zero or negative values can make the search invalid or infinite.
Why Zero Is Dangerous
Suppose:
candidates = [0,2]
target = 4
If 0 is selected repeatedly:
remaining = 4
never changes.
The recursion becomes infinite.
Why Negative Values Are Dangerous
Suppose:
candidates = [-1,2]
target = 4
Selecting -1 increases the remaining target:
remaining = 5
The search may continue indefinitely because candidate reuse is unlimited.
For this problem, candidates should be strictly positive.
Production-Ready Validation
private void validateCandidates(
int[] candidates) {
for (int candidate : candidates) {
if (candidate <= 0) {
throw new IllegalArgumentException(
"Candidates must be positive");
}
}
}
Complete Production-Ready Solution
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class CombinationSumProduction {
public List<List<Integer>> combinationSum(
int[] candidates,
int target) {
if (candidates == null) {
throw new IllegalArgumentException(
"Candidates must not be null");
}
if (target < 0) {
throw new IllegalArgumentException(
"Target must not be negative");
}
validateCandidates(candidates);
int[] sortedCandidates =
Arrays.copyOf(
candidates,
candidates.length);
Arrays.sort(sortedCandidates);
List<List<Integer>> result =
new ArrayList<>();
backtrack(
sortedCandidates,
0,
target,
new ArrayList<>(),
result);
return result;
}
private void backtrack(
int[] candidates,
int start,
int remaining,
List<Integer> current,
List<List<Integer>> result) {
if (remaining == 0) {
result.add(
new ArrayList<>(current));
return;
}
for (int i = start;
i < candidates.length;
i++) {
int candidate =
candidates[i];
if (candidate > remaining) {
break;
}
if (i > start
&& candidate
== candidates[i - 1]) {
continue;
}
current.add(candidate);
backtrack(
candidates,
i,
remaining - candidate,
current,
result);
current.remove(
current.size() - 1);
}
}
private void validateCandidates(
int[] candidates) {
for (int candidate : candidates) {
if (candidate <= 0) {
throw new IllegalArgumentException(
"Candidates must contain only positive values");
}
}
}
}
This implementation also safely handles duplicate candidate values by skipping equal choices at the same recursion level.
Why Copy the Input Before Sorting?
This statement:
Arrays.sort(candidates);
modifies the caller’s array.
In coding challenges, that is usually acceptable.
In production code, unexpected input mutation may be undesirable.
Use:
int[] sortedCandidates =
Arrays.copyOf(
candidates,
candidates.length);
Then sort the copy.
Complexity Analysis
Combination Sum does not have one simple tight complexity expression because the number of valid and invalid search paths depends on:
- The target
- Candidate values
- Number of candidates
- Minimum candidate value
- Number of valid combinations
Let:
m = smallest candidate
T = target
The maximum recursion depth is approximately:
T / m
because selecting the smallest value repeatedly creates the deepest path.
A commonly stated upper bound is exponential:
O(n^(T/m))
where n is the number of candidates.
However, the actual runtime is usually described as output-sensitive and exponential.
Complexity Summary
| Complexity | Value |
|---|---|
| Time | Exponential, output-dependent |
| Maximum Recursion Depth | O(target / minimum candidate) |
| Current Path Space | O(target / minimum candidate) |
| Output Space | Total size of all valid combinations |
Sorting requires:
O(n log n)
before backtracking begins.
Why Is the Complexity Exponential?
At each recursion level, multiple candidates may be selected.
The search tree branches repeatedly until:
- The target reaches zero, or
- The branch exceeds the target
When small candidates and a large target are used, the tree can become very large.
Correctness Intuition
The algorithm is correct because:
- Every recursive path represents a non-decreasing candidate sequence.
- Reusing index
iallows unlimited candidate reuse. - The remaining target precisely tracks how much more is required.
- Only paths reaching
remaining == 0are saved. - Starting from the current index prevents reordered duplicates.
- Backtracking restores state before exploring sibling branches.
- Every valid combination corresponds to one unique path.
Common Interview Mistakes
Mistake 1 — Recursing with i + 1
Incorrect:
backtrack(
candidates,
i + 1,
remaining - candidate,
current,
result);
This prevents candidate reuse.
For Combination Sum, recurse with:
i
Mistake 2 — Starting the Loop from Zero Every Time
This generates reordered duplicates such as:
[2,3,2]
[3,2,2]
Use a start index.
Mistake 3 — Forgetting to Restore the Path
After recursion:
current.remove(
current.size() - 1);
Without this step, sibling branches inherit previous selections.
Mistake 4 — Saving the Mutable Path Directly
Incorrect:
result.add(current);
Correct:
result.add(
new ArrayList<>(current));
Mistake 5 — Forgetting the Target-Zero Base Case
The valid base condition is:
remaining == 0
Mistake 6 — Continuing After Finding a Valid Combination
After saving a valid combination, return immediately.
Candidates are positive, so adding more values would exceed the target.
Mistake 7 — Ignoring Zero or Negative Candidates
Unlimited reuse of non-positive values can produce infinite recursion.
Mistake 8 — Sorting Without Mentioning Input Mutation
Sorting improves pruning but changes the original array unless a copy is made.
Mistake 9 — Using a Set to Deduplicate Every Result
Prevent duplicate branches during generation rather than generating duplicates and hashing entire result lists afterward.
Handling Duplicate Candidate Values
The original problem states that candidates are distinct.
A production variation may contain:
[2,2,3]
Without duplicate pruning, the same combination can be generated through both copies of 2.
Duplicate-Pruning Condition
After sorting:
if (i > start
&& candidates[i]
== candidates[i - 1]) {
continue;
}
This skips equal candidates only when they represent alternative choices at the same recursion level.
Why Same-Level Duplicate Skipping Works
The same candidate may still be reused recursively.
For:
candidate = 2
the recursive call remains at the same index.
This permits:
[2,2,2]
The duplicate check only prevents a second identical array entry from starting an equivalent sibling branch.
Combination Sum II
A common follow-up is LeetCode #40 — Combination Sum II.
Differences:
| Combination Sum | Combination Sum II |
|---|---|
| Candidate reuse allowed | Each array position used once |
Recurse with i |
Recurse with i + 1 |
| Candidates originally distinct | Input may contain duplicates |
| Duplicate pruning usually optional | Duplicate pruning required |
Java Code — Combination Sum II
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class CombinationSumTwo {
public List<List<Integer>> combinationSum2(
int[] candidates,
int target) {
Arrays.sort(candidates);
List<List<Integer>> result =
new ArrayList<>();
backtrack(
candidates,
0,
target,
new ArrayList<>(),
result);
return result;
}
private void backtrack(
int[] candidates,
int start,
int remaining,
List<Integer> current,
List<List<Integer>> result) {
if (remaining == 0) {
result.add(
new ArrayList<>(current));
return;
}
for (int i = start;
i < candidates.length;
i++) {
if (i > start
&& candidates[i]
== candidates[i - 1]) {
continue;
}
int candidate =
candidates[i];
if (candidate > remaining) {
break;
}
current.add(candidate);
backtrack(
candidates,
i + 1,
remaining - candidate,
current,
result);
current.remove(
current.size() - 1);
}
}
}
Combination Sum III
Another variation is LeetCode #216 — Combination Sum III.
Requirements:
- Select exactly
kvalues. - Use numbers from
1through9. - Each number may be used once.
- Sum must equal
target.
The recursive state tracks both:
remaining count
remaining sum
Java Code — Combination Sum III
import java.util.ArrayList;
import java.util.List;
public class CombinationSumThree {
public List<List<Integer>> combinationSum3(
int k,
int target) {
List<List<Integer>> result =
new ArrayList<>();
backtrack(
1,
k,
target,
new ArrayList<>(),
result);
return result;
}
private void backtrack(
int start,
int remainingCount,
int remainingSum,
List<Integer> current,
List<List<Integer>> result) {
if (remainingCount == 0
&& remainingSum == 0) {
result.add(
new ArrayList<>(current));
return;
}
if (remainingCount == 0
|| remainingSum <= 0) {
return;
}
for (int number = start;
number <= 9;
number++) {
if (number > remainingSum) {
break;
}
current.add(number);
backtrack(
number + 1,
remainingCount - 1,
remainingSum - number,
current,
result);
current.remove(
current.size() - 1);
}
}
}
Combination Sum IV
LeetCode #377 — Combination Sum IV asks for the number of ordered sequences that reach the target.
In that problem:
[1,2]
and:
[2,1]
are counted separately.
This is usually solved with dynamic programming rather than generating every sequence.
Combination Sum vs Combination Sum IV
| Combination Sum | Combination Sum IV |
|---|---|
| Return combinations | Return count |
| Order does not matter | Order matters |
| Backtracking | Dynamic programming |
[1,2] equals [2,1] |
They are different |
Approach 3 — Dynamic Programming for Existence
If the requirement is only:
Does at least one combination reach the target?
Use dynamic programming.
Java Code — Existence Check
public class CombinationSumExists {
public boolean canReachTarget(
int[] candidates,
int target) {
boolean[] reachable =
new boolean[target + 1];
reachable[0] = true;
for (int amount = 1;
amount <= target;
amount++) {
for (int candidate : candidates) {
if (candidate <= amount
&& reachable[
amount - candidate]) {
reachable[amount] = true;
break;
}
}
}
return reachable[target];
}
}
This avoids materializing all combinations.
Approach 4 — Count Combinations
If only the number of unordered combinations is required, use a coin-change-style dynamic programming solution.
Java Code — Count Unordered Combinations
public class CombinationSumCount {
public long countCombinations(
int[] candidates,
int target) {
long[] ways =
new long[target + 1];
ways[0] = 1L;
for (int candidate : candidates) {
for (int amount = candidate;
amount <= target;
amount++) {
ways[amount] +=
ways[amount - candidate];
}
}
return ways[target];
}
}
Candidate-first iteration ensures order does not create additional combinations.
Ordered Count Variation
To count ordered sequences, iterate amounts first.
for (int amount = 1;
amount <= target;
amount++) {
for (int candidate : candidates) {
if (candidate <= amount) {
ways[amount] +=
ways[amount - candidate];
}
}
}
This distinction is a common senior-level interview topic.
Approach 5 — Memoized Search for Count
Backtracking may revisit the same remaining target repeatedly.
When only the count is required, memoization can reduce repeated work.
Java Code — Memoized Ordered Count
import java.util.Arrays;
public class CombinationSumMemoizedCount {
public long countOrdered(
int[] candidates,
int target) {
long[] memo =
new long[target + 1];
Arrays.fill(
memo,
-1L);
memo[0] = 1L;
return count(
candidates,
target,
memo);
}
private long count(
int[] candidates,
int remaining,
long[] memo) {
if (memo[remaining] != -1L) {
return memo[remaining];
}
long total = 0L;
for (int candidate : candidates) {
if (candidate <= remaining) {
total += count(
candidates,
remaining - candidate,
memo);
}
}
memo[remaining] = total;
return total;
}
}
Memoization is more useful for counting than for returning every distinct result.
Pruning Techniques
1. Sort Candidates
Sorting allows:
if (candidate > remaining) {
break;
}
2. Skip Duplicate Candidates
if (i > start
&& candidates[i]
== candidates[i - 1]) {
continue;
}
3. Validate Positive Candidates
This prevents infinite recursion.
4. Stop Immediately at Remaining Zero
Do not continue exploring after a valid combination is found.
5. Lower-Bound Pruning
If the smallest candidate is greater than the remaining target, the branch cannot succeed.
Sorting makes this automatic.
6. Greatest Common Divisor Check
A senior-level mathematical optimization is to calculate the GCD of all candidates.
If:
target % gcd != 0
no solution exists.
Example:
candidates = [4,6,10]
gcd = 2
An odd target can never be reached.
GCD Precheck
private int gcd(
int first,
int second) {
while (second != 0) {
int remainder =
first % second;
first = second;
second = remainder;
}
return Math.abs(first);
}
private boolean canPossiblyReach(
int[] candidates,
int target) {
int commonDivisor = 0;
for (int candidate : candidates) {
commonDivisor =
gcd(
commonDivisor,
candidate);
}
return commonDivisor != 0
&& target % commonDivisor == 0;
}
This is optional and mainly useful when inputs are large.
Edge Cases
Target Is Zero
Mathematically, one valid combination exists:
[]
The algorithm returns:
[[]]
Empty Candidate Array
Input:
candidates = []
target = 7
Output:
[]
One Candidate Reaches the Target
candidates = [7]
target = 7
Output:
[
[7]
]
One Candidate Reused
candidates = [2]
target = 8
Output:
[
[2,2,2,2]
]
No Valid Combination
candidates = [4,6]
target = 5
Output:
[]
Candidate Greater Than Target
candidates = [8,10]
target = 7
Output:
[]
Sorting and pruning stop immediately.
Duplicate Candidates
candidates = [2,2,3]
target = 7
Expected unique result:
[
[2,2,3]
]
Use duplicate pruning.
Integer Overflow Consideration
The current algorithm subtracts candidates from the target, so arithmetic overflow is less likely under normal positive constraints.
However:
- Very large target values can produce enormous recursion trees.
- Counting solutions may overflow
intorlong. - Use
BigIntegerif exact counts may exceed 64-bit limits.
Production Applications
Combination Sum-style search appears in:
- Payment denomination selection
- Budget allocation
- Resource composition
- Package construction
- Inventory selection
- Pricing bundles
- Capacity planning
- Test configuration generation
- Workflow component selection
- Manufacturing material composition
Real-World Example — Payment Denominations
Suppose payment denominations are:
[5,10,20]
Target:
40
Possible combinations include:
[5,5,5,5,5,5,5,5]
[10,10,10,10]
[20,20]
[5,5,10,20]
...
This resembles the coin-change problem.
In production payment systems, the goal may instead be:
- Minimize the number of notes
- Count possible combinations
- Enforce inventory limits
- Prefer larger denominations
Those variations may require dynamic programming or bounded search.
Real-World Example — Cloud Resource Bundles
Suppose available instance capacities are:
[2,4,8]
A system needs total capacity:
12
Possible compositions:
[2,2,2,2,2,2]
[4,4,4]
[4,8]
[2,2,8]
...
Additional constraints may include:
- Maximum number of instances
- Regional availability
- Cost limits
- Fault-domain diversity
Backtracking can incorporate these constraints and prune invalid branches.
Real-World Example — Test Configuration
Suppose test modules contribute scenario weights:
[2,3,5]
The testing system needs configurations totaling weight 8.
Possible combinations:
[2,2,2,2]
[2,3,3]
[3,5]
Each valid combination may define a different test scenario.
Bounded Candidate Usage
A production variation may limit how many times each candidate can be used.
Example:
candidate 2 may be used at most 3 times
Track remaining counts or usage frequency in the recursive state.
Java Code — Bounded Usage
import java.util.ArrayList;
import java.util.List;
public class BoundedCombinationSum {
public List<List<Integer>> combinationSum(
int[] candidates,
int[] limits,
int target) {
if (candidates.length
!= limits.length) {
throw new IllegalArgumentException(
"Candidates and limits must match");
}
List<List<Integer>> result =
new ArrayList<>();
backtrack(
candidates,
limits,
0,
target,
new ArrayList<>(),
result);
return result;
}
private void backtrack(
int[] candidates,
int[] limits,
int index,
int remaining,
List<Integer> current,
List<List<Integer>> result) {
if (remaining == 0) {
result.add(
new ArrayList<>(current));
return;
}
if (index == candidates.length
|| remaining < 0) {
return;
}
int candidate =
candidates[index];
int maximumUsage =
Math.min(
limits[index],
remaining / candidate);
for (int usage = 0;
usage <= maximumUsage;
usage++) {
for (int count = 0;
count < usage;
count++) {
current.add(candidate);
}
backtrack(
candidates,
limits,
index + 1,
remaining
- usage * candidate,
current,
result);
for (int count = 0;
count < usage;
count++) {
current.remove(
current.size() - 1);
}
}
}
}
Return Only One Valid Combination
When only one solution is required, return a boolean and stop early.
Java Code — Find One Combination
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class FindOneCombinationSum {
public List<Integer> findOne(
int[] candidates,
int target) {
Arrays.sort(candidates);
List<Integer> current =
new ArrayList<>();
boolean found =
backtrack(
candidates,
0,
target,
current);
return found
? new ArrayList<>(current)
: List.of();
}
private boolean backtrack(
int[] candidates,
int start,
int remaining,
List<Integer> current) {
if (remaining == 0) {
return true;
}
for (int i = start;
i < candidates.length;
i++) {
int candidate =
candidates[i];
if (candidate > remaining) {
break;
}
current.add(candidate);
if (backtrack(
candidates,
i,
remaining - candidate,
current)) {
return true;
}
current.remove(
current.size() - 1);
}
return false;
}
}
Lazy Combination Processing
Storing every result can consume significant memory.
Instead, process each completed combination immediately.
Java Code — Lazy Processor
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.Consumer;
public class LazyCombinationSum {
public void generate(
int[] candidates,
int target,
Consumer<List<Integer>> consumer) {
int[] sorted =
Arrays.copyOf(
candidates,
candidates.length);
Arrays.sort(sorted);
backtrack(
sorted,
0,
target,
new ArrayList<>(),
consumer);
}
private void backtrack(
int[] candidates,
int start,
int remaining,
List<Integer> current,
Consumer<List<Integer>> consumer) {
if (remaining == 0) {
consumer.accept(
List.copyOf(current));
return;
}
for (int i = start;
i < candidates.length;
i++) {
int candidate =
candidates[i];
if (candidate > remaining) {
break;
}
current.add(candidate);
backtrack(
candidates,
i,
remaining - candidate,
current,
consumer);
current.remove(
current.size() - 1);
}
}
}
This lowers retained memory but does not reduce total search work.
Backtracking vs Dynamic Programming
| Backtracking | Dynamic Programming |
|---|---|
| Returns actual combinations | Often returns count, existence, or optimum |
| Easy to add arbitrary constraints | Efficient for repeated states |
| May explore exponential tree | Often pseudo-polynomial |
| Uses choose–explore–unchoose | Uses recurrence and stored results |
| Best when solutions must be listed | Best when only aggregate result is needed |
Combination Sum vs Coin Change
The problems are closely related.
| Combination Sum | Coin Change |
|---|---|
| Return all combinations | Usually minimize coins or count ways |
| Backtracking | Dynamic programming |
| Output may be exponential | Typically O(n × target) |
| Flexible result listing | Efficient aggregate calculation |
Senior-Level Follow-Up Questions
How Would You Return the Minimum-Length Combination?
Use dynamic programming or branch-and-bound.
Track the shortest valid path and prune paths that are already longer than the best solution.
How Would You Return the Combination with Minimum Cost?
If candidates have separate values and costs, track:
- Remaining target
- Current cost
- Best cost
Use branch-and-bound or dynamic programming when states overlap.
Can Memoization Be Used While Returning Every Combination?
Yes, but it is more complicated.
A memo may map:
(start, remaining)
to all suffix combinations.
However:
- Stored results can consume significant memory.
- Lists must be copied carefully.
- Output itself may be exponential.
- Standard backtracking is usually clearer.
Memoization is more useful for counting or existence queries.
How Would You Parallelize the Search?
Top-level candidate branches are independent.
Each branch must use:
- A private current path
- A private result collection
- No shared mutable recursion state
Parallelization may help only when individual branches are expensive.
For small targets, thread overhead usually outweighs the benefit.
What Happens with Floating-Point Candidates?
Avoid direct floating-point equality for target matching.
Options include:
- Convert amounts to integer minor units
- Use
BigDecimal - Define a tolerance carefully
For monetary amounts, cents should usually be stored as integers.
How Would You Handle a Very Large Target?
Generating every combination may be infeasible.
Consider:
- Counting instead of listing
- Dynamic programming
- Finding only one solution
- Finding the minimum number of candidates
- Applying usage limits
- Strong mathematical pruning
- Streaming results
- Distributed search only when justified
Strong Interview Explanation
I sort the candidate values so that I can stop a branch when a candidate exceeds the remaining target. I use a start index to ensure combinations are generated in non-decreasing order, preventing reordered duplicates. At each step, I choose a candidate, subtract it from the remaining target, and recurse from the same index because reuse is allowed. When the remaining target becomes zero, I copy the current path into the result. After recursion, I remove the last value to restore state. The runtime is exponential and output-dependent, while the maximum recursion depth is approximately target divided by the smallest candidate.
Interview Tips
Interviewers commonly ask:
- Why recurse using the same index?
- Why is a start index required?
- How are duplicate combinations prevented?
- Why does sorting help?
- When can the loop break?
- Why must candidates be positive?
- What happens when the target is zero?
- What is the maximum recursion depth?
- How is Combination Sum II different?
- How would you count combinations instead of returning them?
- How would you find only one combination?
- Can memoization help?
- How would you handle duplicate candidate values?
- How would you support bounded candidate usage?
- How does candidate-first vs amount-first DP affect ordering?
Unit Tests
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;
import java.util.List;
import org.junit.jupiter.api.Test;
class CombinationSumOptimizedTest {
private final CombinationSumOptimized solution =
new CombinationSumOptimized();
@Test
void shouldFindCombinationsForSeven() {
List<List<Integer>> result =
solution.combinationSum(
new int[]{2, 3, 6, 7},
7);
assertEquals(
2,
result.size());
assertTrue(
result.contains(
List.of(2, 2, 3)));
assertTrue(
result.contains(
List.of(7)));
}
@Test
void shouldFindCombinationsForEight() {
List<List<Integer>> result =
solution.combinationSum(
new int[]{2, 3, 5},
8);
assertEquals(
3,
result.size());
assertTrue(
result.contains(
List.of(2, 2, 2, 2)));
assertTrue(
result.contains(
List.of(2, 3, 3)));
assertTrue(
result.contains(
List.of(3, 5)));
}
@Test
void shouldReturnEmptyWhenNoCombinationExists() {
List<List<Integer>> result =
solution.combinationSum(
new int[]{2},
1);
assertTrue(
result.isEmpty());
}
@Test
void shouldReuseCandidate() {
List<List<Integer>> result =
solution.combinationSum(
new int[]{2},
8);
assertEquals(
List.of(
List.of(2, 2, 2, 2)),
result);
}
@Test
void shouldReturnEmptyCombinationForZeroTarget() {
List<List<Integer>> result =
solution.combinationSum(
new int[]{2, 3},
0);
assertEquals(
List.of(List.of()),
result);
}
}
Unit Tests for Production Validation
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
import static org.junit.jupiter.api.Assertions.assertThrows;
import org.junit.jupiter.api.Test;
class CombinationSumProductionTest {
private final CombinationSumProduction solution =
new CombinationSumProduction();
@Test
void shouldNotModifyInput() {
int[] candidates =
{7, 2, 3, 6};
int[] original =
candidates.clone();
solution.combinationSum(
candidates,
7);
assertArrayEquals(
original,
candidates);
}
@Test
void shouldRejectZeroCandidate() {
assertThrows(
IllegalArgumentException.class,
() -> solution.combinationSum(
new int[]{0, 2},
4));
}
@Test
void shouldRejectNegativeCandidate() {
assertThrows(
IllegalArgumentException.class,
() -> solution.combinationSum(
new int[]{-1, 2},
4));
}
}
Approach Comparison
| Approach | Returns | Typical Complexity | Best Use |
|---|---|---|---|
| Basic backtracking | All combinations | Exponential | Understand recursion |
| Sorted and pruned backtracking | All combinations | Exponential but reduced search | Preferred interview solution |
| Dynamic programming existence | Boolean | O(n × target) | Check feasibility |
| Dynamic programming count | Number of ways | O(n × target) | Count combinations |
| Memoized recursion | Count or feasibility | O(n × target), state-dependent | Repeated subproblems |
| Lazy backtracking | Streams combinations | Exponential | Reduce retained output memory |
Summary
Combination Sum extends standard combination backtracking by allowing candidates to be reused.
The key differences are:
Base condition
remaining target == 0
and:
Recursive index
i instead of i + 1
The start index prevents reordered duplicates, while recursion from the same index allows unlimited candidate reuse.
Sorting improves the algorithm by enabling early pruning.
The search remains exponential because the number of possible combinations depends on the target and candidate values.
Key Takeaways
- Combination Sum is a target-based backtracking problem.
- Candidates may be reused unlimited times.
- Use a start index to prevent reordered duplicates.
- Recurse with
ito reuse the current candidate. - Recurse with
i + 1only when reuse is not allowed. - Track the remaining target instead of recalculating sums.
- Save a result when the remaining target becomes zero.
- Copy the mutable path before storing it.
- Remove the last choice after recursion.
- Sort candidates to enable early pruning.
- Break when a candidate exceeds the remaining target.
- Require positive candidates to ensure recursion terminates.
- Skip same-level duplicate values when input may contain duplicates.
- Combination Sum II uses each candidate once.
- Dynamic programming is better for count, existence, or optimization variants.
- Use lazy processing when storing every result is unnecessary.
- The recursion depth depends on the target and smallest candidate.
- Real systems usually add budget, inventory, count, or optimization constraints.