Problem Statement

Combination Sum

You are given a list of different numbers called candidates and one target number. Your job is to find every group of numbers from the list that adds up exactly to the target. You can use the same number as many times as you want. For example, if 2 is in the list, you are allowed to use 2 over and over. Each group you return should be unique, so [2, 2, 3] and [3, 2, 2] count as the same group and you only keep one of them.

mediumBacktrackingBacktrackingTime: O(n^(t/m)) · Space: O(t/m)

Signals to notice

find combinations summing to targetcan reuse elementsunlimited supply

Brute force first

Not applicable — enumeration IS the problem. But naive recursion without pruning explores dead branches. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.

The key insight

Backtracking with pruning: sort candidates, start from current index (allowing reuse), subtract from remaining target. Stop when target < 0 or target = 0 (found a valid combination). The sort enables early termination. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

Trace it on `candidates=[2,3,6,7], target=7`

sort -> [2,3,6,7]; backtrack(start=0, cur=[], rem=7)
pick 2 -> cur=[2,2,2], rem=1; 2>1 so break, pop; pick 3 -> rem=0 -> record [2,2,3]
back to rem=5, i=1: pick 3 -> rem=2; 3>2 break; dead end
back to rem=7, i=1: pick 3 -> cur=[3,3], rem=1; break; pop; dead end
rem=7, i=2: 6 -> rem=1 break/pop; i=3: pick 7 -> rem=0 -> record [7]
loop ends; return result = [[2,2,3],[7]]

What must stay true

By always choosing from index i or later (not earlier), you avoid generating the same combination in different orders. Sorting lets you prune: if candidates[j] > remaining, skip j and everything after. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

sort(candidates)
function backtrack(start, current, remaining):
  if remaining == 0: record copy of current; return
  for i from start to end:
    if candidates[i] > remaining: break   # pruned (sorted)
    current.add(candidates[i]); backtrack(i, current, remaining-candidates[i]); current.removeLast()
backtrack(0, [], target)

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Generating duplicates like [2,3,2] and [2,2,3] — always choose from the current index onward. Also, not sorting means you can't prune branches early. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Backtracking Pattern