SyntaxPilot
Courses/DSA and Coding Problems/Lesson 32
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 32 of 90

Combination sum

queued

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:

  1. Sort the candidates.
  2. Only build combinations in non-decreasing order: after a 3 you may add another 3 or something bigger, never a 2.
  3. Pass a start index: the next choice is c[start] or later. The loop runs from start, not 0.
  4. In version I recurse with i, not i + 1, because the same coin may be reused.
  5. 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:

  1. Each number once: recurse with i + 1.
  2. 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

  1. Combination Sum III (LeetCode 216): pick k distinct digits from 1 to 9 that add up to n.
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]].

  1. 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.

  1. 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.

  1. 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

  1. 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.
  2. Version I recurses with i, version II with i + 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.
  3. Why i > start and not i > 0 in the duplicate check? The rule is "try each value once per level". i == start is 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).
  4. Why sort first? Pruning with break needs increasing values, and the duplicate skip needs equal values next to each other.
  5. What is pruning? Cutting off a branch of the recursion early because it cannot lead to an answer (here: c[i] > rem).
  6. Why do we add new ArrayList<>(cur) and not cur? cur is one mutable list shared by the whole search; backtracking keeps changing it, so the answer must be a snapshot.
  7. 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.
  8. 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 + Set patch, 26 crore calls and TLE for target 50.
  • Sort, pass a start index, and prune with break when c[i] > rem: each combination is built once, in sorted order. Version I recurses with i (reuse), version II with i + 1.
  • Version II skips a repeated value at the same level: if (i > start && c[i] == c[i - 1]) continue;. Always save new 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).