· By John Kavanagh

Backtracking Decision Trees: Solving 'Combination Sum'

A photograph of an interior wooden staircase with glass balustrades and geometric wall panels.
Image by Ariel Domenden.

Combination Sum is a very good backtracking problem because the search tree is much easier to see than it is in grid‑based questions. In Word Search, the backtracking happens across positions in a board. Here, it happens across choices:

  • take this candidate again
  • move on to the next candidate
  • stop because the remaining sum is gone or impossible

That makes it a cleaner backtracking example. The recursion is still real, but the decision tree is easier to visualise.


What the Problem is Really Asking

We are given:

  • a list of candidate numbers
  • a target total

For this implementation, the candidates must be distinct positive integers and the target must be non‑negative; allowing zero or negative reusable candidates would invalidate the termination argument. We need every unique combination of candidates that adds up to the target. Candidates can be reused as many times as we like, but the order inside a combination does not matter, so [2, 2, 3] and [3, 2, 2] count as the same answer.

That last sentence matters a lot. It means this is not a plain subset problem.

If the candidates are:

[2, 3, 6, 7]

and the target is:

7

then valid answers include:

  • [7]
  • [2, 2, 3]

The Clumsy Brute‑Force Shape

A first recursive answer often ends up doing something like:

  • branch on including or skipping a candidate
  • keep exploring even when the remaining sum has already gone negative
  • generate many dead ends before ruling them out

That is not wrong, but it can feel quite loose. It tends to spend a lot of time wandering into branches we could have eliminated earlier with a bit more structure.


The Better Framing: A Growing Path and a Remaining Total

The backtracking version becomes much calmer if each recursive call answers this question:

  • starting from this candidate index, how can I complete the remaining total?

That naturally gives us three pieces of state:

  • the current startIndex
  • the remaining total
  • the current combination we are building

Sorting the candidates first helps as well, because once a candidate is bigger than the remaining total, every later candidate will be too.


A Practical TypeScript Solution

The implementation below sorts the candidates once, builds one combination in place, and stops exploring a branch as soon as the next candidate is too large for the remaining total.

export const combinationSum = (
  candidates: number[],
  target: number
): number[][] => {
  const sortedCandidates = [...candidates].sort((left, right) => {
    return left - right;
  });
  const result: number[][] = [];
  const current: number[] = [];

  const search = (startIndex: number, remaining: number): void => {
    if (remaining === 0) {
      result.push([...current]);
      return;
    }

    for (
      let index = startIndex;
      index < sortedCandidates.length;
      index += 1
    ) {
      const candidate = sortedCandidates[index];

      if (candidate > remaining) {
        break;
      }

      current.push(candidate);
      search(index, remaining - candidate);
      current.pop();
    }
  };

  search(0, target);

  return result;
};

Why search(index, ...) is the important detail

Notice that recursive call:

search(index, remaining - candidate);

not:

search(index + 1, ...)

That is what allows candidate reuse. If we pick 2, we are still allowed to pick 2 again on the next level.

If the problem said each number could only be used once, then the recursion would move to index + 1 instead.

That one line is carrying a lot of meaning.


Why Sorting is More than a Convenience

Sorting is doing two useful jobs here.

First, sorting puts the candidate values in increasing order. When the search only moves forwards through those indices, it avoids generating rearrangements such as:

  • [2, 3, 2]
  • [3, 2, 2]

The index rule is what prevents reordered duplicates. For distinct candidates, it works even if their values are unsorted. Sorting also makes each resulting combination non‑decreasing in value.

Second, it enables pruning:

  • if candidate > remaining, we can stop the loop immediately

That keeps the recursion much tidier than blindly exploring impossible branches.

The recursion depth depends on reuse, not just on the number of candidates. Let c be the candidate count and D be the target divided by the smallest candidate, rounded down. Every choice reduces the remaining total by at least that smallest positive value, so a path contains at most D values. The official bounds keep D at most 20, but that bound matters when adapting the function to larger targets.

The working copy takes O(c) space, and the current path and recursive calls take O(D), giving O(c + D) auxiliary space apart from sorting workspace and returned combinations. Under the usual O(c log c) comparison‑sort model, total time is O(c log c + S + L), where S counts candidate checks across the search and L counts values copied into successful results. JavaScript does not specify a sort complexity. The search can grow exponentially with depth; it is not a simple once‑per‑candidate subset search. Storing the returned combinations also costs O(L).


Another Workable Answer: Include‑or‑Skip Recursion

There is another backtracking style people often write first. At each index, we decide:

  • include this candidate
  • or skip to the next candidate

That can work too, but it tends to be noisier here because it spreads the "reuse the same candidate" logic across a more awkward branch structure.

It often ends up looking like this conceptually:

  • use the current candidate and stay on this index
  • or do not use it and move on

That version is fine, but I think the for‑loop backtracking answer is better because it mirrors the combination‑building process more directly. We are not really making a binary yes‑or‑no choice on each candidate in isolation. We are exploring the next valid options from the current position in the search tree.


What About Dynamic Programming?

You can solve related problems with dynamic programming, especially if the goal is:

  • count the number of ways
  • or ask only whether some solution exists

For Combination Sum, where we want the actual combinations themselves, backtracking is the cleaner fit. We are enumerating concrete paths, not just computing a numeric answer.


Why This is Backtracking but Not Brute Force in the Lazy Sense

It is easy to dismiss any recursive search as brute force, but that misses the structure here.

This solution is doing two disciplined things:

  • it never generates reordered duplicates because the search only moves forwards through candidate indices
  • it stops early when the sorted candidate list proves the remaining branch cannot work

That is real pruning, not just blind enumeration.


Common Mistakes

Moving to index + 1 when reuse is allowed

That accidentally turns the problem into the single‑use variant, where each candidate can appear at most once.

Forgetting to pop() after the recursive call

Then one branch leaks state into the next branch, which is the classic backtracking bug.

Keeping the early break without sorting

Only moving forwards through candidate indices prevents reordered duplicates. Sorting serves a different purpose here: once a candidate exceeds the remaining total, every later value will too, so the early break is valid. Without sorting, a later candidate could still fit.


Which Solution is Best?

I prefer sorted backtracking with pruning here because the path follows the combinations we need to return. The include‑or‑skip recursion is still valid, but it is a less tidy way to express the same search. Dynamic programming can be useful for related variants, though I would not lead with it when the task is to return all combinations.

The cost we cannot prune away is writing the combinations themselves. If a variant allows many more answers, the result can dominate memory even when the active path stays short.

The Part Worth Remembering

  • Backtracking here is really about building a path through a decision tree.
  • Passing index rather than index + 1 is what allows candidate reuse.
  • Sorting makes the early break valid; the forward‑only index rule prevents reordered duplicates.

Combination Sum is a good backtracking problem because the recursion is visible rather than slippery. We can almost draw the tree by hand, which makes the logic much easier to trust.


Looking for technical direction?

I support teams that need senior judgement on React, Next.js, headless CMS architecture, performance, migrations, and technical SEO.