Start learning free

LESSON 351 OF 535 · BACKTRACKING

Combination Sum in C++: Backtracking over Sorted Candidates

Practice O(nt/m) Read the full explanation

Given a vector of distinct integers candidates and an integer target, return every combination of numbers from candidates that adds up to target.

The same number may be chosen any number of times. Two combinations are the same when they use the same numbers the same number of times, whatever the order: [2, 2, 3] and [3, 2, 2] are one combination, and it must appear only once.

Write the numbers of each combination in ascending order, and return the combinations in lexicographic order: compare two combinations number by number, and the first position where they differ decides which one comes first. If no combination adds up to target, return an empty vector.

 

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation: 2 + 2 + 3 = 7, using the 2 twice, and 7 alone is 7.
No other combination adds up to 7. [2,2,3] comes first because its first number, 2, is smaller than 7.

Example 2:

Input: candidates = [5,2,3], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Explanation: The candidates are not sorted, but every combination is written in ascending order.
[2,2,2,2] and [2,3,3] both start with 2; at their second number, 2 is smaller than 3. [3,5] starts with 3, so it comes last.

Example 3:

Input: candidates = [2], target = 1
Output: []
Explanation: The only candidate, 2, is already bigger than 1, so no combination adds up to 1.

 

Constraints:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • All the numbers in candidates are distinct.
  • 1 <= target <= 40

Note:

The tutorial uses backtracking. Sort candidates, then build a combination one number at a time: try every candidate from the position of the last number chosen onward (that same number included, since numbers can repeat), go deeper with what is left of target, then remove the number again and try the next one. Starting from the last chosen position builds each combination exactly once, already in ascending order, and the combinations come out in lexicographic order. Because the candidates are sorted, the loop can stop at the first one that is bigger than what is left.

The search is exponential: with n candidates, a target t and a smallest candidate m, a combination has at most t / m numbers, and each of them is one of n candidates, so the time is O(nt/m) in the worst case. Besides the answer, the extra space is O(t / m): the combination being built and one call per number in it.

STEP 1 OF 13
    Ctrl + Enter to check

    C++ · BACKTRACKING

    Combination Sum in C++, explained

    Problem overview

    The method combinationSum receives candidates, a vector of distinct integers, and a target. It returns every combination of candidates that adds up to target. A candidate may be used any number of times. Two combinations are the same if they use the same numbers the same number of times, in any order, so [2, 2, 3] and [3, 2, 2] are one combination and appear once.

    Each combination is written in ascending order, and the combinations are returned in lexicographic order: compare number by number, and the first difference decides. If nothing adds up to target, the result is an empty vector.

    With candidates = [2, 3, 6, 7] and target = 7 the answer is [[2, 2, 3], [7]]. With the unsorted [5, 2, 3] and target 8 it is [[2, 2, 2, 2], [2, 3, 3], [3, 5]]. With [2] and target 1 it is empty, because the only candidate is bigger than the target.

    Approach: build combinations one number at a time

    This is a search over choices, and backtracking fits it. Build a combination by adding one number at a time. After each addition, ask the same question again with a smaller target, which is the amount still needed. When that amount reaches exactly 0, the numbers chosen so far are a valid combination. After exploring a choice, remove the number and try the next candidate in its place.

    Two ideas keep the output correct and small:

    • Sort the candidates, and only look forward. A call receives an index i and may use only candidates from i on. Choosing candidates[j] passes j, not j + 1, to the next call, so the same number can be picked again, but a smaller one never can. Every combination is therefore built in ascending order, exactly once: [2, 2, 3] is found and [3, 2, 2] never is.
    • Stop early. Because the candidates are sorted, as soon as one is bigger than the remaining amount, all the later ones are too, so the loop can break.

    Trying candidates in increasing order and going deeper before moving on also produces the combinations in lexicographic order, which is the order the answer needs.

    The search is exponential. With n candidates, target t and smallest candidate m, a combination has at most t / m numbers, each one of n candidates, so the time is O(n^(t/m)) in the worst case. The stopping rule prunes much of that.

    Step by step

    1. Sort candidates in place with sort(candidates.begin(), candidates.end()). This gives the ascending combinations, the right order of results, and the early stop.
    2. Create result, a vector<vector<int>>, empty, to collect the combinations.
    3. Create current, a vector<int>, empty: the combination being built.
    4. Start the search by calling backtrack with target as the amount still needed and 0 as the first usable index.
    5. Return result. backtrack filled the same vector.
    6. Write backtrack with the parameters remaining and i next to the vectors, all vectors taken by reference. It returns nothing and adds to result instead.
    7. Detect a full combination: if remaining == 0, the numbers in current add up to target.
    8. Record it with push_back(current) and return. Every candidate is at least 2, so adding more could only overshoot.
    9. Loop over the candidates from j = i to the end: those the combination may take next.
    10. Break when too big: if candidates[j] > remaining, no later candidate fits either.
    11. Choose: push_back(candidates[j]) onto current.
    12. Explore: call backtrack with remaining - candidates[j] and j as the first index.
    13. Undo: pop_back() removes the number just chosen, so current is what it was before this turn of the loop.

    The solution in C++

    class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> result;
        vector<int> current;
        backtrack(candidates, target, 0, current, result);
        return result;
    }

    void backtrack(vector<int>& candidates, int remaining, int i, vector<int>& current, vector<vector<int>>& result) {
        if (remaining == 0) {
            result.push_back(current);
            return;
        }
        for (int j = i; j < candidates.size(); j++) {
            if (candidates[j] > remaining) {
                break;
            }
            current.push_back(candidates[j]);
            backtrack(candidates, remaining - candidates[j], j, current, result);
            current.pop_back();
        }
    }
};

    C++ details worth a closer look:

    • References. backtrack takes current and result by reference, so every call works on the same two vectors. The caller sees the changes, and no vector is copied per call.
    • push_back(current) copies. The vector inside result is a copy of current at that moment. That is why later push_back and pop_back calls on current do not change the stored combinations.
    • sort changes the caller's vector. candidates is a non-const reference, so the vector passed in comes back sorted. For this lesson that is fine.
    • Unsigned bound. j < candidates.size() compares an int with an unsigned value. It is safe because j never goes below 0.
    • Pop after every push. Each loop turn pushes one number and pops it again, so current is restored even after a deep search.

    Complexity

    Time: O(n^(t/m)) in the worst case, where n is the number of candidates, t the target and m the smallest candidate. A combination holds at most t / m numbers, and each position has up to n choices. The break and the forward-only index cut this down, but the bound is exponential. Copying each answer into result costs extra time proportional to its length. The sort adds O(n log n), which is small next to the search.

    Space: O(t / m) besides the output. current holds at most t / m numbers, and the recursion is at most that many calls deep.

    Edge cases and common mistakes

    • No combination. [2] with target 1 returns []: the loop breaks at once and nothing is recorded. [2] with target 3 gives [] too, because the search reaches a remaining amount of 1 and breaks.
    • Using the same number more than once. [2] with target 4 returns [[2, 2]]. Passing j + 1 instead of j would forbid that.
    • Starting every loop at 0. The search would produce [2, 3] and [3, 2] as separate answers. Starting at i lists each combination once.
    • Unsorted input. Without the sort, [5, 2, 3] would give combinations in the wrong order, and the early break would stop at the 5 and miss answers. The sort is part of the algorithm.
    • Skipping the undo. Without pop_back(), current keeps growing and every later answer contains leftovers from earlier branches.
    • Checking the sum late. Passing the remaining amount down, instead of summing current at every call, keeps each step a constant-time comparison.
    • Target equal to a candidate. The single-number combination counts: for [2, 3, 6, 7] and 7, [7] is an answer.

    Testing

    • candidates = [2, 3, 6, 7], target = 7 gives [[2, 2, 3], [7]].
    • candidates = [5, 2, 3], target = 8 gives [[2, 2, 2, 2], [2, 3, 3], [3, 5]].
    • candidates = [2], target = 1 gives [].
    • candidates = [2, 3, 5], target = 8 gives [[2, 2, 2, 2], [2, 3, 3], [3, 5]].
    • candidates = [7, 3, 2], target = 3 gives [[3]].
    • candidates = [2], target = 4 gives [[2, 2]].
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free