logo

Solving the Combination Sum Series with One Template

1928 words

This article covers the Combination Sum series of problems, four in total:

  • 39. Combination Sum (Medium)
  • 40. Combination Sum II (Medium)
  • 216. Combination Sum III (Medium)
  • 377. Combination Sum IV (Medium)

Our series has already covered three rounds of backtracking content. In the previous two articles, we discussed in detail the classic subset, permutation, and combination problems of backtracking, along with the candidate set concept and pruning techniques:

That wraps up our introduction to the fundamentals of backtracking. This article is an exercise session where we use the LeetCode Combination Sum series as an example, solving the entire series with one code template and making minor tweaks for each problem based on its specific conditions. In backtracking problems, subtle differences in conditions can lead to changes in the code approach. For the Combination Sum series, the conditions we need to handle are:

  • With replacement vs. without replacement
  • With duplicate elements vs. without duplicate elements
  • Whether the combination size is restricted

We will walk through how to tweak the code for each of these conditions below.

General Solution for Combination Sum

Let’s first write a general solution for the Combination Sum problem, then adjust the code for each specific problem later.

The standard Combination Sum problem (each problem in the LeetCode series has slight differences from it):

Given an array candidates and a target number target, find all unique combinations in candidates where the numbers sum to target.

Notes:

  • The array candidates contains no duplicate elements.
  • All numbers (including target) are positive integers.
  • Combinations are unordered — different orderings of the same set are considered the same combination.

The Combination Sum problem is very similar to the Combination problem. Once you’ve mastered the Combination problem (you can review this article), writing the Combination Sum code becomes straightforward. Add a target parameter to the backtracking function — each time an element x is chosen, pass target - x into the next recursive call. When target reaches 0, we’ve found a combination that sums to target. Here is the solution code:

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Deque<Integer> current = new ArrayDeque<>();
    List<List<Integer>> res = new ArrayList<>();
    backtrack(candidates, 0, target, current, res);
    return res;
}

// Candidate set: candidates[m..N)
void backtrack(int[] candidates, int m, int target, Deque<Integer> current, List<List<Integer>> res) {
    if (target < 0) {
        return;
    } else if (target == 0) {
        res.add(new ArrayList<>(current));
        return;
    }

    // Similar to the Combinations problem, ascending order is needed
    for (int i = m; i < candidates.length; i++) {
        // Choose the number candidates[i]
        current.addLast(candidates[i]);
        // Elements candidates[m..i) are all invalidated
        backtrack(candidates, i+1, target - candidates[i], current, res);
        // Undo the choice       
        current.removeLast();
    }
}

Note that Combination Sum does not restrict the number of elements in a combination, so there is no parameter k in the backtracking code. Remember this code — all the following solutions will be minor tweaks based on it.

Variations of the Problem

Now let’s look at how each of the four LeetCode problems varies from the standard Combination Sum problem, and how to solve them accordingly.

With Replacement vs. Without Replacement

Problem: LeetCode 39 - Combination Sum (Medium)

What’s different: Elements in the array can be chosen an unlimited number of times.

Being allowed to choose repeatedly is essentially sampling with replacement.

In the standard problem, array elements cannot be reused — it’s sampling without replacement. For the array candidates, if the current choice is candidates[i], the candidate set for the next round becomes candidates[i+1..N).

For the with-replacement variant, we can “put back” the current element candidates[i] into the candidate set, making the next round’s candidate set candidates[i..N). This way, candidates[i] can still be chosen later.

We only need to adjust the recursive call parameter in the original code, changing the next round’s candidate set from candidates[i+1..N) to candidates[i..N). Here is the solution code:

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Deque<Integer> current = new ArrayDeque<>();
    List<List<Integer>> res = new ArrayList<>();
    backtrack(candidates, 0, target, current, res);
    return res;
}

// Candidate set: candidates[m..N)
void backtrack(int[] candidates, int m, int target, Deque<Integer> current, List<List<Integer>> res) {
    if (target < 0) {
        return;
    } else if (target == 0) {
        res.add(new ArrayList<>(current));
        return;
    }

    for (int i = m; i < candidates.length; i++) {
        // Choose the number candidates[i]
        current.addLast(candidates[i]);
        // Code adjustment: recursive call parameter
        // Pass i instead of the original i+1
        // This way, candidates[i] remains in the candidate set after being chosen and can be selected again
        backtrack(candidates, i, target - candidates[i], current, res);
        // Undo the choice       
        current.removeLast();
    }
}

With Duplicate Elements vs. Without Duplicate Elements

Problem: LeetCode 40 - Combination Sum II (Medium)

What’s different: The array may contain duplicate elements.

When the array contains duplicate elements, we need to eliminate duplicate results. For example, given the array [1,2,2][1, 2, 2] and target of 3, if we label the two 22s as 212_1 and 222_2, then [1,21][1, 2_1] and [1,22][1, 2_2] are duplicate results and only one should be kept.

We already covered the problem of duplicate elements in backtracking in the previous article, and presented deduplication strategies for subset, permutation, and combination problems (to review the previous article, click here). The deduplication strategy for Combination Sum can directly follow the one used for the Combination problem:

  1. Before backtracking, sort the array elements so that equal elements are adjacent;
  2. When there are multiple equal elements, only choose the first one among them.

We only need to adjust the candidate element traversal in the original code. If candidates[i] equals the previous element, it means it’s not the first among equal elements, so we skip it. Here is the solution code:

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);
    Deque<Integer> current = new ArrayDeque<>();
    List<List<Integer>> res = new ArrayList<>();
    backtrack(candidates, 0, target, current, res);
    return res;
}

// Candidate set: candidates[m..N)
void backtrack(int[] candidates, int m, int target, Deque<Integer> current, List<List<Integer>> res) {
    if (target < 0) {
        return;
    } else if (target == 0) {
        res.add(new ArrayList<>(current));
    }

    for (int i = m; i < candidates.length; i++) {
        // Code adjustment: candidate set traversal
        if (i > m && candidates[i] == candidates[i-1]) {
            // If candidates[i] equals the previous element, it's not the first among equal elements — skip it.
            continue;
        }
        // Choose the number candidates[i]
        current.addLast(candidates[i]);
        // Elements candidates[m..i) are all invalidated
        backtrack(candidates, i+1, target - candidates[i], current, res);
        // Undo the choice   	
        current.removeLast();
    }
}

Restricting to k-Combinations

LeetCode 216 - Combination Sum III (Medium)

What’s different: The result must be a k-combination, meaning exactly k elements that sum to target.

In the previous problems, there was no restriction on the number of elements in a combination. This problem requires the combination to contain exactly k numbers. This actually brings us back to the standard “choose kk from nn” combination problem — we need to add a parameter k to the backtracking function, and only collect a result when the combination size reaches k and the sum equals target.

Another difference in this problem is that there’s no input array; instead, we choose from the numbers 1 through 9. This change is easy to handle — just a minor adjustment to the recursive parameters.

Here is the solution code:

public List<List<Integer>> combinationSum3(int k, int n) {
    Deque<Integer> current = new ArrayDeque<>();
    List<List<Integer>> res = new ArrayList<>();
    backtrack(k, 1, n, current, res);
    return res;
}

// Candidate set: integers [m..9]
// Code adjustment: added parameter k
void backtrack(int k, int m, int target, Deque<Integer> current, List<List<Integer>> res) {
    if (target < 0) {
        return;
    } else if (target == 0) {
        // Code adjustment: only collect results when the chosen set has exactly k elements
        if (current.size() == k) {
            res.add(new ArrayList<>(current));
        }
        return;
    }
    if (current.size() > k) {
        return;
    }
    
    // Choose from the candidate set
    for (int i = m; i <= 9; i++) {
        // Choose the number i
        current.addLast(i);
        // Numbers [m..i) are all invalidated
        backtrack(k, i+1, target - i, current, res);
        // Undo the choice
        current.removeLast();
    }
}

Backtracking vs. Dynamic Programming

Problem: LeetCode 377 - Combination Sum IV (Medium)

What’s different: …wait, hasn’t this turned into a completely different problem?

This problem is actually quite deceptive. Let’s re-read the problem statement:

Given an array of distinct positive integers, find the number of possible combinations that add up to a positive integer target.

Example: nums = [1, 2, 3], target = 4. All possible combinations are:

(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations. Therefore the output is 7.

“Different sequences are counted as different combinations” — this has departed from the concept of combinations and become permutations! So this problem is actually a Permutation Sum problem, not Combination Sum. Since that’s the case, we can’t just apply the Combination Sum template anymore.

We solved the first three Combination Sum problems using one template. This fourth problem is where LeetCode sets its trap. This problem is not a backtracking problem at all — using backtracking will result in Time Limit Exceeded (TLE). This reminds us that we shouldn’t fall into fixed thinking patterns when solving problems; we need to carefully analyze the problem’s conditions.

Once we realize this, we’ll see that this problem is a pure dynamic programming problem. Looking more closely, it’s essentially the coin change problem:

LeetCode 322 - Coin Change (Medium)

Given coins of different denominations and a total amount. Write a function to compute the fewest number of coins needed to make up that amount. If no combination of coins can make up the amount, return -1. You may assume you have an infinite supply of each coin denomination.

Example:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

It’s just that “array” has become “coins” and target has become amount. So the solution for this problem can follow the coin change approach.

Summary

The Combination Sum series is an excellent set of practice problems for backtracking. It reinforces the concepts of candidate elements and pruning that we covered earlier, while also letting us experience how different variations of a problem affect the code. Backtracking problems are endlessly varied — subtle differences in conditions can turn it into a completely different problem (it might even shift from backtracking to dynamic programming, as with the fourth problem in the series). So when solving problems, we must pay close attention to the details. When encountering a backtracking problem in an interview, make sure to clarify all conditions with the interviewer before writing code.

As a preview, the backtracking series will take a brief pause here. Coming up next, we’ll cover a few articles on binary trees and DFS/BFS — stay tuned!