Definition
Combination Sum finds all unique multisets of candidate numbers summing to a target with unlimited reuse.
- Remaining target drives the recursion: when it reaches zero a valid combination is found.
- Start index ensures candidates are tried in non-decreasing index order, preventing reordered duplicates.
- Reuse is allowed by passing the same index (not index + 1) on recursion.
- Pruning stops a branch when the remaining target goes negative or when the current candidate exceeds it.
- Sorting the candidates enables early termination via a break when a candidate is too large.
At National Bank of India, a customer wants to reach an exact savings target using fixed denomination deposits, and the same denomination can be deposited many times. We want every distinct set of deposits that hits the target exactly. We try adding each denomination, allow repeats, and only move forward through the list so the same set is never counted in a different order.
Understanding the Concepts
What is the Combination Sum Problem?
Given a set of distinct positive numbers (candidates) and a target, find all unique combinations of candidates that sum to the target. Each candidate may be used an unlimited number of times. Two combinations are the same if they contain the same numbers in any order.
At National Bank of India, Rajesh wants to reach a savings goal of 15,000 rupees using deposits of 2,000, 3,000, and 5,000 rupees, where each denomination can be deposited any number of times.
package com.bank.service;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class CombinationSum {
public static List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> result = new ArrayList<>();
backtrack(candidates, target, 0, new ArrayList<>(), result);
return result;
}
private static void backtrack(int[] candidates, int remaining, int start,
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 (candidates[i] > remaining) break; // prune: sorted, so all after are larger
current.add(candidates[i]);
backtrack(candidates, remaining - candidates[i], i, current, result); // same i allows reuse
current.remove(current.size() - 1);
}
}
public static void main(String[] args) {
int[] denominations = {2000, 3000, 5000};
int target = 15000;
List<List<Integer>> combos = combinationSum(denominations, target);
System.out.println("Ways to reach " + target + ":");
for (List<Integer> combo : combos) {
System.out.println(combo);
}
}
}
Ways to reach 15000:
[2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000]
Wait -- that is not right for 15000. Let me recalculate...
Actually, 8 times 2000 is 16000, not 15000. Let me use a cleaner example:
package com.bank.service;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class CombinationSumDemo {
public static List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> result = new ArrayList<>();
backtrack(candidates, target, 0, new ArrayList<>(), result);
return result;
}
private static void backtrack(int[] candidates, int remaining, int start,
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 (candidates[i] > remaining) break;
current.add(candidates[i]);
backtrack(candidates, remaining - candidates[i], i, current, result);
current.remove(current.size() - 1);
}
}
public static void main(String[] args) {
int[] denominations = {2, 3, 5};
int target = 8;
List<List<Integer>> combos = combinationSum(denominations, target);
System.out.println("Ways to reach " + target + " (in thousands):");
for (List<Integer> combo : combos) {
System.out.println(combo);
}
}
}
Ways to reach 8 (in thousands):
[2, 2, 2, 2]
[2, 3, 3]
[3, 5]
Why Does This Problem Matter?
Combination Sum combines two independent concerns: unlimited reuse of elements and uniqueness of output. Understanding how these are handled separately prepares you for related problems like Combination Sum II (each element used once) and Coin Change (count instead of enumerate).
In banking, this pattern applies when Priya at ICICI needs to find all ways to construct a specific payment amount from fixed denomination instruments.
package com.bank.service;
public class CombinationSumUseCases {
// Related problems:
// Combination Sum II: each candidate used at most once -> pass i+1 and skip duplicates
// Coin Change: count combinations instead of listing -> DP approach
// Combination Sum III: pick K numbers from 1-9 summing to target
}
How Does the Start Index Prevent Duplicates?
The start index ensures that at each recursion level, we only try candidates from the current index onward. This means every combination is built in non-decreasing index order, so [2, 3] is generated but [3, 2] is never generated as a separate combination.
Without the start index, we would produce both [2, 3, 3] and [3, 2, 3] and [3, 3, 2], which are the same multiset.
package com.bank.core;
import java.util.ArrayList;
import java.util.List;
public class StartIndexExplained {
// WITHOUT start index: produces duplicates
public static void wrongBacktrack(int[] cands, int remaining, List<Integer> current, List<List<Integer>> result) {
if (remaining == 0) { result.add(new ArrayList<>(current)); return; }
for (int i = 0; i < cands.length; i++) { // always starts at 0!
if (cands[i] > remaining) continue;
current.add(cands[i]);
wrongBacktrack(cands, remaining - cands[i], current, result);
current.remove(current.size() - 1);
}
}
// WITH start index: no duplicates
public static void correctBacktrack(int[] cands, int remaining, int start, List<Integer> current, List<List<Integer>> result) {
if (remaining == 0) { result.add(new ArrayList<>(current)); return; }
for (int i = start; i < cands.length; i++) {
if (cands[i] > remaining) break;
current.add(cands[i]);
correctBacktrack(cands, remaining - cands[i], i, current, result);
current.remove(current.size() - 1);
}
}
}
How Does Reuse Work via the Same Index?
Passing i (the same index) rather than i + 1 on recursion is what allows a candidate to be reused. The recursive call can pick the same candidate again because the loop starts from i, not i + 1. This is the single line that distinguishes unlimited reuse from single use.
// Unlimited reuse: pass i (same index)
backtrack(candidates, remaining - candidates[i], i, current, result);
// Single use (Combination Sum II): pass i + 1
backtrack(candidates, remaining - candidates[i], i + 1, current, result);
How Is This Different from Combination Sum II?
| Aspect | Combination Sum (Reuse) | Combination Sum II (No Reuse) |
|---|---|---|
| Element usage | Unlimited | Each element at most once |
| Recursive call | Pass same index i | Pass i + 1 |
| Input duplicates | Not applicable (distinct) | Must skip duplicate candidates |
| Duplicate skipping | Start index alone | Start index + sort + skip equal siblings |
package com.bank.core;
public class CombSumComparison {
// Combination Sum: reuse allowed
// backtrack(cands, rem - cands[i], i, ...)
// Combination Sum II: no reuse, skip duplicates
// if (i > start && cands[i] == cands[i-1]) continue;
// backtrack(cands, rem - cands[i], i + 1, ...)
}
What Are the Edge Cases?
The main edge cases are: target is zero (one valid combination: the empty set), no candidates can reach the target (empty result), and a single candidate that divides the target evenly.
package com.bank.core;
import java.util.List;
public class CombSumEdgeCases {
public static void main(String[] args) {
// Target 0: one empty combination
System.out.println(CombinationSumDemo.combinationSum(new int[]{2, 3}, 0));
// Output: [[]]
// No valid combination
System.out.println(CombinationSumDemo.combinationSum(new int[]{5}, 3));
// Output: []
// Single candidate divides target
System.out.println(CombinationSumDemo.combinationSum(new int[]{3}, 9));
// Output: [[3, 3, 3]]
}
}
[[]]
[]
[[3, 3, 3]]
What About Using BigDecimal for Money?
In a real banking application, amounts must use BigDecimal rather than int to avoid floating-point rounding errors. The comparison uses compareTo instead of ==.
package com.bank.service;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
public class CombinationSumBigDecimal {
public static void backtrack(BigDecimal[] candidates, BigDecimal remaining, int start,
List<BigDecimal> current, List<List<BigDecimal>> result) {
if (remaining.compareTo(BigDecimal.ZERO) == 0) {
result.add(new ArrayList<>(current));
return;
}
for (int i = start; i < candidates.length; i++) {
if (candidates[i].compareTo(remaining) > 0) break;
current.add(candidates[i]);
backtrack(candidates, remaining.subtract(candidates[i]), i, current, result);
current.remove(current.size() - 1);
}
}
}
What Are Common Interview Follow-Up Questions?
Interviewers commonly ask these follow-ups:
- Combination Sum II: each candidate used at most once, with duplicate candidates in the input.
- Combination Sum III: pick exactly K numbers from 1-9 that sum to a target.
- Coin Change: count the number of combinations instead of listing them (use DP).
- What is the time complexity? The worst case is exponential, bounded by the number of valid combinations times the target divided by the smallest candidate.
package com.bank.core;
public class CombSumComplexity {
// Time: O(N^(T/M)) where T is target and M is minimum candidate
// Space: O(T/M) for recursion depth
// Each level branches into N candidates, depth is at most T/M
}
Visual Overview
Backtracking Tree for candidates [2, 3, 5], target 8: remaining=8 ├── pick 2, remaining=6 │ ├── pick 2, remaining=4 │ │ ├── pick 2, remaining=2 │ │ │ ├── pick 2, remaining=0 -> RECORD [2,2,2,2] │ │ │ ├── pick 3 > 2 -> prune │ │ ├── pick 3, remaining=1 │ │ │ ├── pick 3 > 1 -> prune │ ├── pick 3, remaining=3 │ │ ├── pick 3, remaining=0 -> RECORD [2,3,3] │ ├── pick 5, remaining=1 │ │ └── 5 > 1 -> prune ├── pick 3, remaining=5 │ ├── pick 3, remaining=2 │ │ └── 3 > 2 -> prune │ ├── pick 5, remaining=0 -> RECORD [3,5] ├── pick 5, remaining=3 │ └── 5 > 3 -> prune Result: [2,2,2,2], [2,3,3], [3,5]
Key Takeaway
Combination Sum finds all distinct combinations of candidate numbers that sum to a target, where each candidate may be reused any number of times. I solve it with backtracking driven by a remaining target and a start index. If the remaining target hits zero I record the current combination. If it would go negative I prune. Otherwise I loop over candidates from the start index, and for each one I subtract it and recurse with the same index rather than the next one, which allows unlimited reuse.
The device that prevents duplicates is the start index. Because I never consider a candidate earlier than the current start, every combination is built in non-decreasing index order, so the same multiset is never produced in a different order. I also sort the candidates so I can break out of the loop as soon as one exceeds the remaining target.
At National Bank of India I used this to help a customer like Rajesh reach an exact savings goal using fixed deposit denominations that could each be used many times, enumerating every distinct set of deposits that hit the goal. In a real implementation, all amounts would be BigDecimal and comparisons would use compareTo.
The two independent concerns are reuse (controlled by passing i vs i + 1) and uniqueness (controlled by the start index). Understanding these separately prepares you for Combination Sum II, Combination Sum III, and the Coin Change DP variants.
Remember one sentence: allow reuse by passing the same index, prevent duplicates with a start index that only moves forward.
---