Combination Sum

Return combinations that add to a target. A value may be used more than once.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Combination Sum: Carry the remaining target, reuse the current sorted index, and break when the next choice is too large.

Input and goalReturn combinations that add to a target. A value may be used more than once.

Initialize sorted choicesPositive unique choices remain [2,3,6,7]; call choose(0,7) with an empty path.

[]active call07

inputcandidates = [2,3,6,7], target = 7columnspath | start | remainingactionchoices = [2,3,6,7]answer[]

Recognize it

Use this pattern when combinations must sum to a target, order should not duplicate answers, and the same positive candidate may be selected repeatedly.

Keep true

Every path is nondecreasing by choice index, sum(path) + remaining equals the original target, and choose(start, remaining) may use only start or later indices; remaining zero is exactly a solution.

Reuse it

For reusable combination search, carry a decreasing feasibility measure and a nondecreasing choice boundary; sorted positive choices turn the first oversized option into a safe loop break.

Pattern: Backtracking with a remaining target.

Simple idea: Choose values in sorted index order. Reuse the same index when repeats are allowed. Stop when the next value is larger than the remaining target.

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
   choices = sorted({num for num in candidates if num > 0})
   answer: list[list[int]] = []
   path: list[int] = []

   def choose(start: int, remaining: int) -> None:
      if remaining == 0:
         answer.append(path.copy())
         return

      for index in range(start, len(choices)):
         num = choices[index]
         if num > remaining:
            break
         path.append(num)
         choose(index, remaining - num)
         path.pop()

   choose(0, target)
   return answer

Cost: Exponential time in the worst case and $O(target)$ call-stack space when the smallest choice is 1.