Backtracking Decision Trees: Solving 'Combination Sum'

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

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. Candidates can be reused as many times as we like.

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, it makes the combinations grow in a stable order, which helps avoid duplicate arrangements such as:

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

We keep combinations non‑decreasing by never going backwards in the candidate list.

Second, it enables pruning:

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

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

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.

Skipping the Sort and Then Wondering Where Duplicate Permutations Came from

Sorting keeps each combination in non‑decreasing order, which prevents reordered duplicates, and it makes the early break valid once candidate > remaining.

Which Solution is Best?

For this problem, the sorted backtracking solution with pruning is the best answer. 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.

For Combination Sum, the best final answer is sorted backtracking with a growing path.

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 lets us prune impossible branches and avoid 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.