Combination Sum

Find every combination of candidates (reuse allowed, order ignored) that sums exactly to a target. Try adding each candidate ≥ the last one used (to avoid duplicate orderings), recursing on the reduced target.

Category: Backtracking
Time complexity: O(2ⁿ)
Space complexity: O(target/min)

Pseudocode

for each candidate ≥ last used
  add it, recurse on target − candidate
  remaining = 0 ⇒ record combination
  remaining < 0 ⇒ prune, backtrack

Reference implementation

def solve(start, remaining, path):
    if remaining == 0: out.append(path[:]); return
    if remaining &lt; 0: return
    for i in range(start, len(cands)):
        path.append(cands[i])
        solve(i, remaining - cands[i], path)
        path.pop()

Open the interactive Combination Sum visualisation →