These are the notes for DSA episode 32, one of the most asked backtracking problems. Given some numbers (the candidates) and a target, list every combination of candidates that adds up to exactly the target. In version I (LeetCode 39) a number can be reused any number of times; in version II (LeetCode 40) each number in the input is used at most once, and the input can contain duplicates. The obvious way tries any number at every step: it prints the same combination in several orders, and even after patching that with a Set, a target of 50 with six candidates makes 26 crore recursive calls and times out. The fix is one extra parameter: a start index, so every combination is built exactly once, in sorted order, plus pruning on the sorted input. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
A parking machine only takes coins and gives no change. You have a big pile of ₹2, ₹3, ₹6 and ₹7 coins, as many of each as you like. The ticket costs exactly ₹7. In how many different ways can you pay? 2 + 2 + 3 and 7: two ways. 3 + 2 + 2 is the same payment as 2 + 2 + 3: the machine does not care about the order the coins go in.
Version II: now you pay with the coins in your pocket: 10, 1, 2, 7, 6, 1, 5. Each coin can be used once, and you have two ₹1 coins. Paying ₹8: 1 + 1 + 6, 1 + 2 + 5, 1 + 7, 2 + 6. 1 + 7 with the first ₹1 coin and with the second ₹1 coin is the same payment, so it is listed once.
| At the machine | In the code |
|---|---|
| The coin values you can use | candidates (the array c) |
| The ticket price | target |
| The amount still to pay | rem |
| The coins dropped in so far | cur (the current list) |
| One way to pay, order ignored | one combination |
| "Never go back to a smaller coin" | the start index |
Problem statement
Combination Sum (LeetCode 39). Given an array of distinct positive integers candidates and a positive integer target, return all unique combinations of candidates whose sum is target. The same number may be chosen an unlimited number of times. Two combinations are the same if they use the same numbers the same number of times (order does not matter).
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]]
candidates = [2], target = 1 → []
Combination Sum II (LeetCode 40). Same, but candidates may contain duplicates and each element may be used at most once. The answer must not contain duplicate combinations.
candidates = [10, 1, 2, 7, 6, 1, 5], target = 8 → [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
candidates = [2, 5, 2, 1, 2], target = 5 → [[1, 2, 2], [5]]
Edge cases: a target smaller than every candidate ([]), a single candidate ([1], target 3 → [[1, 1, 1]]), unsorted input ([7, 3, 2], target 7 → [[2, 2, 3], [7]]), and in version II a value repeated many times ([1, 1, 1], target 2 → [[1, 1]], once).
Brute force: any coin at any step
Straight from episode 31's backtracking (choose → explore → un-choose): rem is the amount still to pay. If it is 0, save a copy of the coins. Otherwise try every coin that still fits: add it, recurse with rem - x, remove it.
static void brute(int[] c, int rem, List<Integer> cur,
List<List<Integer>> out) {
if (rem == 0) {
out.add(new ArrayList<>(cur));
return;
}
for (int x : c) {
if (x > rem) continue;
cur.add(x);
brute(c, rem - x, cur, out);
cur.remove(cur.size() - 1);
}
}
For [2, 3, 6, 7], target 7, it printed:
[[2, 2, 3], [2, 3, 2], [3, 2, 2], [7]]
Wrong: the same payment three times, in three orders.
The patch: sort each answer and keep a Set
if (rem == 0) {
List<Integer> s = new ArrayList<>(cur);
Collections.sort(s);
out.add(s); // out is a Set<List<Integer>> (LinkedHashSet)
return;
}
Now it prints [[2, 2, 3], [7]]. Correct. (A LinkedHashSet keeps one copy of each list and remembers the order they were added; two Lists are equal when they hold the same elements in the same order.)
The big input: target 50
Candidates {2, 3, 5, 7, 11, 13}, target 50: Time Limit Exceeded. Measured on the same machine without a time limit:
| Target | Brute force calls | Time | Combinations found |
|---|---|---|---|
| 20 | 2,268 | 9 ms | 25 |
| 40 | 54,08,941 (54 lakh) | 1 s | 206 |
| 50 | 26,41,58,295 (26 crore) | 28 s | 453 |
Why the brute force fails
At every step it tries every coin, so it builds every order of the same coins: [2, 2, 3], [2, 3, 2] and [3, 2, 2] are three separate branches of the search. A combination of k different coins can be built in up to k! orders (10 different coins: 36,28,800 orders of one answer). The Set hides the duplicates in the output, but the work to build them has already been done.
The key insight: build every combination in sorted order
Every combination has exactly one sorted order. So:
- Sort the candidates.
- Only build combinations in non-decreasing order: after a 3 you may add another 3 or something bigger, never a 2.
- Pass a start index: the next choice is
c[start]or later. The loop runs fromstart, not 0. - In version I recurse with
i, noti + 1, because the same coin may be reused. - Pruning: the list is sorted, so if
c[i] > rem, every later coin is bigger too:break, don't just skip. Pruning means cutting off a whole branch of the search early because it can't lead to an answer.
The recursion tree for combo([2, 3, 6, 7], 7):
[ ] need 7
├── +2 → [2] need 5
│ ├── +2 → [2,2] need 3
│ │ ├── +2 → [2,2,2] need 1 (dead end: 2 > 1, break)
│ │ └── +3 → [2,2,3] need 0 ✓
│ └── +3 → [2,3] need 2 (dead end: 3 > 2, break)
│ (6 > 5: break, pruned)
├── +3 → [3] need 4
│ └── +3 → [3,3] need 1 (dead end; 2 is never tried again: no [3,2,2])
├── +6 → [6] need 1 (dead end)
└── +7 → [7] need 0 ✓
Two answers, each built exactly once: no Set, no sorting at the end. For target 50 the optimal version makes 5,381 calls instead of 26 crore.
The optimal solution in Java
import java.util.*;
public class Main {
static void go(int[] c, int start, int rem, List<Integer> cur,
List<List<Integer>> res) {
if (rem == 0) {
res.add(new ArrayList<>(cur));
return;
}
for (int i = start; i < c.length; i++) {
if (c[i] > rem) break;
cur.add(c[i]);
go(c, i, rem - c[i], cur, res);
cur.remove(cur.size() - 1);
}
}
static List<List<Integer>> combo(int[] c, int target) {
Arrays.sort(c);
List<List<Integer>> res = new ArrayList<>();
go(c, 0, target, new ArrayList<>(), res);
return res;
}
public static void main(String[] args) {
System.out.println(combo(new int[]{2, 3, 6, 7}, 7));
System.out.println(combo(new int[]{2, 3, 5}, 8));
System.out.println(combo(new int[]{2}, 1));
System.out.println(combo(new int[]{1}, 3));
System.out.println(combo(new int[]{7, 3, 2}, 7));
}
}
Output:
[[2, 2, 3], [7]]
[[2, 2, 2, 2], [2, 3, 3], [3, 5]]
[]
[[1, 1, 1]]
[[2, 2, 3], [7]]
Target 50 with {2, 3, 5, 7, 11, 13} printed 453 ways, 8 ms.
Combination Sum II: each number once, duplicates in the input
Two changes to the same code:
- Each number once: recurse with
i + 1. - Duplicates: sort (equal values sit side by side), then at one level of the tree (inside one loop) try each value only once:
if (i > start && c[i] == c[i - 1]) continue;
i == start is the first choice in this loop, so it is always allowed, even if the previous element has the same value: that element was chosen one level up. This is how [1, 1, 6] survives while the second [1, 7] is skipped.
static void go2(int[] c, int start, int rem, List<Integer> cur,
List<List<Integer>> res) {
if (rem == 0) {
res.add(new ArrayList<>(cur));
return;
}
for (int i = start; i < c.length; i++) {
if (i > start && c[i] == c[i - 1]) continue;
if (c[i] > rem) break;
cur.add(c[i]);
go2(c, i + 1, rem - c[i], cur, res);
cur.remove(cur.size() - 1);
}
}
static List<List<Integer>> combo2(int[] c, int target) {
Arrays.sort(c);
List<List<Integer>> res = new ArrayList<>();
go2(c, 0, target, new ArrayList<>(), res);
return res;
}
combo2({10, 1, 2, 7, 6, 1, 5}, 8), combo2({2, 5, 2, 1, 2}, 5) and combo2({1, 1, 1}, 2) printed:
[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
[[1, 2, 2], [5]]
[[1, 1]]
The same solutions in C++
#include <bits/stdc++.h>
using namespace std;
void go(vector<int>& c, int start, int rem, vector<int>& cur, vector<vector<int>>& res) {
if (rem == 0) { res.push_back(cur); return; }
for (int i = start; i < (int)c.size(); i++) {
if (c[i] > rem) break; // sorted: every later coin is bigger
cur.push_back(c[i]);
go(c, i, rem - c[i], cur, res); // i: the same coin may be reused
cur.pop_back();
}
}
vector<vector<int>> combo(vector<int> c, int target) {
sort(c.begin(), c.end());
vector<vector<int>> res; vector<int> cur;
go(c, 0, target, cur, res);
return res;
}
void go2(vector<int>& c, int start, int rem, vector<int>& cur, vector<vector<int>>& res) {
if (rem == 0) { res.push_back(cur); return; }
for (int i = start; i < (int)c.size(); i++) {
if (i > start && c[i] == c[i - 1]) continue; // same value, same level: skip
if (c[i] > rem) break;
cur.push_back(c[i]);
go2(c, i + 1, rem - c[i], cur, res); // i + 1: each coin once
cur.pop_back();
}
}
vector<vector<int>> combo2(vector<int> c, int target) {
sort(c.begin(), c.end());
vector<vector<int>> res; vector<int> cur;
go2(c, 0, target, cur, res);
return res;
}
void print(const vector<vector<int>>& r) {
cout << "[";
for (size_t i = 0; i < r.size(); i++) {
cout << (i ? ", [" : "[");
for (size_t j = 0; j < r[i].size(); j++) cout << (j ? ", " : "") << r[i][j];
cout << "]";
}
cout << "]\n";
}
int main() {
print(combo({2, 3, 6, 7}, 7));
print(combo({2, 3, 5}, 8));
print(combo({2}, 1));
print(combo2({10, 1, 2, 7, 6, 1, 5}, 8));
print(combo2({2, 5, 2, 1, 2}, 5));
}
In C++, res.push_back(cur) already copies the vector, so the "forgot to copy" bug below cannot happen there.
The same solutions in Python
def combo(c, target):
c = sorted(c)
res, cur = [], []
def go(start, rem):
if rem == 0:
res.append(cur[:]) # a copy, not cur itself
return
for i in range(start, len(c)):
if c[i] > rem:
break # sorted: prune the rest
cur.append(c[i])
go(i, rem - c[i]) # i: reuse allowed
cur.pop()
go(0, target)
return res
def combo2(c, target):
c = sorted(c)
res, cur = [], []
def go(start, rem):
if rem == 0:
res.append(cur[:])
return
for i in range(start, len(c)):
if i > start and c[i] == c[i - 1]:
continue # same value at the same level
if c[i] > rem:
break
cur.append(c[i])
go(i + 1, rem - c[i]) # i + 1: each number once
cur.pop()
go(0, target)
return res
print(combo([2, 3, 6, 7], 7))
print(combo([2, 3, 5], 8))
print(combo([2], 1))
print(combo2([10, 1, 2, 7, 6, 1, 5], 8))
print(combo2([2, 5, 2, 1, 2], 5))
Both print the same five lines as the Java version.
Three real bugs
Bug 1: go(c, i + 1, ...) in version I
Habit from version II. Each coin can now be used only once, so reuse is lost:
combo({2, 3, 6, 7}, 7) → [[7]]
combo({2, 3, 5}, 8) → [[3, 5]]
Fix: recurse with i in version I.
Bug 2: i > 0 instead of i > start in version II
if (i > 0 && c[i] == c[i - 1]) continue;
The second equal value is now banned everywhere, even one level down, where it is the first choice of its loop:
combo2({10, 1, 2, 7, 6, 1, 5}, 8) → [[1, 2, 5], [1, 7], [2, 6]] (no [1, 1, 6])
combo2({2, 5, 2, 1, 2}, 5) → [[5]] (no [1, 2, 2])
combo2({1, 1, 1}, 2) → [] (no [1, 1])
Bug 3: res.add(cur) without a copy
combo({2, 3, 6, 7}, 7) → [[], []]
Both entries are the same list object; every un-choose removes from it, and at the end it is empty. Save a snapshot: res.add(new ArrayList<>(cur)).
Complexity
Let n = number of candidates, T = target, m = smallest candidate.
| Approach | Time | Extra space | Target 50, 6 coins |
|---|---|---|---|
Any coin at any step + sort + Set |
every order of every combination: explodes | the Set of answers |
26 crore calls, TLE |
| Backtracking + start index + pruning (I) | O(n^(T/m + 1)) worst case; in practice about (number of answers × their length) plus dead ends | O(T/m) recursion depth + the output | 5,381 calls, 8 ms |
| Backtracking + skip duplicates (II) | O(2ⁿ · n) worst case (each number in or out, copy each answer) + O(n log n) sort | O(n) depth + the output | — |
Backtracking is still exponential in the worst case, because the answer itself can be exponentially large; no algorithm that lists every combination can beat the size of its output. If you only need the number of combinations, dynamic programming does it in O(n · T) (see practice question 2).
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
Loop from 0 instead of start |
[[2, 2, 3], [2, 3, 2], [3, 2, 2], [7]] |
every order of the same coins is built | for (int i = start; ...) |
go(c, i + 1, ...) in version I |
[[7]] |
each coin can only be used once | go(c, i, ...) |
i > 0 && c[i] == c[i - 1] in version II |
[[1, 2, 5], [1, 7], [2, 6]] |
equal values banned one level down too | i > start && ... |
res.add(cur) |
[[], []] |
one list object, emptied by backtracking | res.add(new ArrayList<>(cur)) |
| Forgetting to sort | break stops too early; duplicates not adjacent |
pruning and skipping need sorted input | Arrays.sort(c) first |
continue instead of break on c[i] > rem |
correct, just slower | the later, bigger coins are still tried | break (input is sorted) |
Sort + Set to remove duplicates |
TLE on bigger targets | the duplicates are still built | start index |
Mini project: exact change at the canteen
Your college canteen machine takes ₹1, ₹2, ₹5 and ₹10 coins and gives no change. Write a program that lists every way to pay ₹20, prints how many there are, and prints the way that uses the fewest coins. (Real output: 40 ways; the fewest is [10, 10].) Extension: read the coin values and the price from input, and print each way as 10 + 5 + 5.
Practice
- Combination Sum III (LeetCode 216): pick
kdistinct digits from 1 to 9 that add up ton.
Solution
Candidates are 1..9 (already sorted, no duplicates), each used once (d + 1), and stop when the list has k numbers.
static void go3(int k, int start, int rem, List<Integer> cur, List<List<Integer>> res) {
if (cur.size() == k) { if (rem == 0) res.add(new ArrayList<>(cur)); return; }
for (int d = start; d <= 9; d++) {
if (d > rem) break;
cur.add(d);
go3(k, d + 1, rem - d, cur, res);
cur.remove(cur.size() - 1);
}
}
k = 3, n = 7 → [[1, 2, 4]]; k = 3, n = 9 → [[1, 2, 6], [1, 3, 5], [2, 3, 4]].
- Count the ways only (no lists). Can you make it faster?
Solution
This is the "coin change ways" dynamic programming problem: ways[s] = number of combinations that pay s. Looping over coins on the outside counts each combination once (order ignored).
static long countWays(int[] c, int target) {
long[] ways = new long[target + 1];
ways[0] = 1;
for (int coin : c)
for (int s = coin; s <= target; s++) ways[s] += ways[s - coin];
return ways[target];
}
{2, 3, 5, 7, 11, 13}, 50 → 453; {2, 3, 6, 7}, 7 → 2. O(n · T) time, O(T) space.
- Print each payment as
2 + 2 + 3.
Solution
static void pretty(int[] c, int start, int rem, Deque<Integer> cur) {
if (rem == 0) {
StringJoiner sj = new StringJoiner(" + ");
for (int x : cur) sj.add(String.valueOf(x));
System.out.println(sj);
return;
}
for (int i = start; i < c.length && c[i] <= rem; i++) {
cur.addLast(c[i]);
pretty(c, i, rem - c[i], cur);
cur.removeLast();
}
}
Sorted {2, 3, 6, 7}, 7 prints 2 + 2 + 3 and 7.
- Subsets II (LeetCode 90): all subsets of an array that may contain duplicates, each subset once.
Solution
The same "skip a repeated value at the same level" rule; every node of the tree is an answer.
static void sub(int[] a, int start, List<Integer> cur, List<List<Integer>> res) {
res.add(new ArrayList<>(cur));
for (int i = start; i < a.length; i++) {
if (i > start && a[i] == a[i - 1]) continue;
cur.add(a[i]);
sub(a, i + 1, cur, res);
cur.remove(cur.size() - 1);
}
}
Sorted {1, 2, 2} → [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]].
Quick quiz
System.out.println(combo2(new int[]{1, 2, 1, 2}, 3));
[[1, 2]][[1, 2], [1, 2]][[1, 2], [1, 2], [1, 2], [1, 2]][]
Answer
[[1, 2]]. Sorted: 1, 1, 2, 2. At the top level the second 1 is skipped. Under the first 1, the first 2 pays exactly 3 and the second 2 is skipped at that level. (Real output: [[1, 2]].)
Interview questions
- How do you avoid duplicate combinations without a Set? Sort, and pass a start index so every combination is built in non-decreasing order, exactly once.
- Version I recurses with
i, version II withi + 1. Why? In I a number can be reused, so the next choice may be the same index; in II each element is used once, so the next choice starts after it. - Why
i > startand noti > 0in the duplicate check? The rule is "try each value once per level".i == startis the first choice at this level, so it is allowed even if the previous element has the same value (that one was chosen at the level above). - Why sort first? Pruning with
breakneeds increasing values, and the duplicate skip needs equal values next to each other. - What is pruning? Cutting off a branch of the recursion early because it cannot lead to an answer (here:
c[i] > rem). - Why do we add
new ArrayList<>(cur)and notcur?curis one mutable list shared by the whole search; backtracking keeps changing it, so the answer must be a snapshot. - What is the time complexity? Exponential in the worst case, roughly O(n^(T/m)) for version I and O(2ⁿ · n) for version II; the output itself can be that large. Space is the recursion depth, O(T/m) or O(n), plus the output.
- How would you only count the combinations? Coin-change-ways DP in O(n · T).
Glossary
| Term | Meaning |
|---|---|
| Combination | A choice of items where the order does not matter ([2, 2, 3] = [3, 2, 2]) |
| Permutation | An arrangement where the order matters (episode 31) |
| Candidates | The numbers you may pick from |
| Target | The exact sum to reach |
rem |
The amount still left to reach the target |
| Backtracking | Build a solution step by step: choose, explore (recurse), un-choose, then try the next choice |
| Recursion tree | A picture of every recursive call: the root is the first call, each child is one choice |
| Start index | The position the next choice may start from; it stops the search from going back to smaller items |
| Pruning | Cutting off a branch of the search early because it can't lead to an answer |
| Dead end | A call that can't reach the target (every remaining candidate is too big) |
| Same level | The choices made inside one loop of one call (siblings in the recursion tree) |
LinkedHashSet |
A Java Set that keeps one copy of each item and remembers insertion order |
| Snapshot / copy | new ArrayList<>(cur): a separate list with the same items at this moment |
| Time Limit Exceeded (TLE) | Too slow for the judge's limit (8 s in the SyntaxPilot compiler) |
| Dynamic programming | Solving a problem by storing answers to smaller sub-problems (used to count the ways) |
Summary
- A combination ignores order. Trying any coin at every step builds every order of the same answer: duplicates, and even with a sort +
Setpatch, 26 crore calls and TLE for target 50. - Sort, pass a start index, and prune with
breakwhenc[i] > rem: each combination is built once, in sorted order. Version I recurses withi(reuse), version II withi + 1. - Version II skips a repeated value at the same level:
if (i > start && c[i] == c[i - 1]) continue;. Always savenew ArrayList<>(cur). - Exponential in the worst case (the output can be that big); O(T/m) or O(n) recursion depth.
Next episode: N-Queens (hard).