Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Combination Sum

LeetCode #39Medium
Reuse allowed; prune when the sum overshoots

Given an array of distinct candidate numbers and a target, return all unique combinations of candidates that sum to the target, where each candidate may be reused an unlimited number of times.

Asked atAmazonMetaUber
step 1 / 27
reuse allowed; prune when the sum overshoots
[2,2,2,2] r=-1
[2,2,2] r=1
[2,2,3] r=0
[2,2,6] r=-3
[2,2] r=3
[2,3,3] r=-1
[2,3] r=2
[2,6] r=-1
[2] r=5
[3,3,3] r=-2
[3,3] r=1
[3,6] r=-2
[3] r=4
[6,6] r=-5
[6] r=1
[7] r=0
ε r=7
combinations
(none yet)
Backtracking · non-decreasing picks with overshoot pruning
▸
1combo(start, rem, path):
2    if rem == 0: record path; return       // exact hit
3    for i in start..n−1:
4        if cand[i] > rem: prune; continue   // overshoot
5        path.push(cand[i])                  // choose
6        combo(i, rem − cand[i], path)       // explore (reuse: i, not i+1)
7        path.pop()                          // un-choose
8    return
state
  • candidates[2, 3, 6, 7]
  • target7

line 1Find every combination of [2, 3, 6, 7] that sums to 7. Numbers may be reused. We track the REMAINING target: start at 7 and subtract each number we pick. The tree below is the full space of picks; r is the remaining target at each node.