Pattern visualizer

Combination Sum

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. Animated on: candidates = [2, 3, 6, 7], target = 7 — find all unique combinations summing to target (candidates may be chosen repeatedly)..

Unbounded backtracking with sum-based pruning

time O(2^t)space O(t/min)step 1 / 11

line 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

Where to practice Backtracking

Practice Backtracking problems All Backtracking problems Back to roadmap