DSA Tracker

Visualize

Combination Sum

Unbounded backtracking with sum-based pruning

time O(2^t)space O(t/min)

Because numbers may be used an unlimited number of times, after choosing candidates[i], the recursive call stays at index i rather than moving to i+1. To avoid duplicate combinations in different orders, we only branch to indices >= i. The search tree is pruned immediately whenever the running sum exceeds the target (remain < 0), guaranteeing we never explore hopeless branches. When remain === 0, the current combination is recorded.

Details

Animated on: candidates = [2, 3, 6, 7], target = 7 — find all unique combinations summing to target (candidates may be chosen repeatedly).

Problem:Combination SumMedium

Pattern:Backtracking Basics

Unbounded backtracking with sum-based pruning

step 1 / 11

Start combinationSum: candidates=[2, 3, 6, 7], target=7. Initialize comb=[], remain=7.

Pseudocode
1FUNCTION combinationSum(candidates, target):
2  ans = empty list of results, comb = empty current combination
3  FUNCTION backtrack(start, remain):
4    IF remain equals 0: add a copy of comb to ans; RETURN
5    IF remain < 0: RETURN   (prune: overshot the target)
6    FOR i from start to (the length of candidates) - 1:
7      add candidates[i] to comb
8      backtrack(i, remain - candidates[i])   (stay at i so it can be reused)
9      remove the last value from comb   (undo the choice)
10    END FOR
11  backtrack(0, target); RETURN ans

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. Start combinationSum: candidates=[2, 3, 6, 7], target=7. Initialize comb=[], remain=7.
  2. Try candidates[0]=2: push 2 → comb=[2]. remain becomes 7-2=5. Recurse at start=0 (repeats allowed).
  3. Choose 2 again: push 2 → comb=[2, 2]. remain becomes 5-2=3. Recurse at start=0.
  4. Choose 2 a third time: push 2 → comb=[2, 2, 2]. remain becomes 3-2=1. Recurse at start=0.
  5. Trying another 2 gives remain = 1-2 = -1 < 0 (sum 8 > 7). Prune branch and backtrack.
  6. Pop 2, back to [2, 2]. Try candidates[1]=3: push 3 → comb=[2, 2, 3]. remain = 3-3=0. Match found! Record [2, 2, 3].
  7. Backtrack to comb=[2]. Try candidates[1]=3 → comb=[2, 3], remain=2. Next choices (3, 6, 7) all exceed 2 (pruned).
  8. Backtrack to comb=[]. Try candidates[1]=3 → comb=[3], remain=4. Next choice 3 gives [3, 3] with remain=1; 3 exceeds 1 (pruned).
  9. Backtrack to comb=[]. Try candidates[2]=6 → comb=[6], remain=1. Next candidates (6, 7) both exceed 1 (pruned).
  10. Backtrack to comb=[]. Try candidates[3]=7: push 7 → comb=[7]. remain = 7-7=0. Match found! Record [7].
  11. Search complete. Return unique combinations summing to 7: [[2, 2, 3], [7]].

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Combination Sum in the editorAll Backtracking problemsBack to roadmap