Combination Sum

Medium#39pick with repeats

You get a list of different positive numbers, the candidates, and a target. Return every combination of candidates that adds up to the target, where a candidate may be used any number of times; two combinations with the same numbers in another order count as one. Our example: [4, 5, 3] and 8 give [3, 5] and [4, 4].

39 Combination SumWalkthrough · 1×

Example: the sums to 8 from [4, 5, 3]. Watch [3, 3] with 2 left: 3 is too big, so the loop breaks at once, since 4 and 5 after it are bigger still.

[ ]33,33,43,544,45candidates041523path—results—
not reached yeton the way herethis stepadds up to the target, or leads to a sum that doescut off: bigger than what is leftdead end, or before start: out of reach

Find every way to add up to 8 with [4, 5, 3], each number as often as you like

01/36
restart · back · play · step
Speed
1function combinationSum(candidates, target):
2 sort(candidates)
3 path = []
4 results = []
5 pick(0, target)
6 return results
7
8function pick(start, left):
9 if left == 0:
10 add copy of path to results
11 return
12 for i from start to len(candidates) - 1:
13 if candidates[i] > left: break // rest bigger
14 path.add(candidates[i])
15 pick(i, left - candidates[i]) // reuse allowed
16 path.removeLast()
state
candidates
[4, 5, 3]
start
–
left
–
i
–
path
–
results
–
click a step to go back

← → step · space play/pause

Why it works

  1. The call below gets i, not i + 1, so the same candidate may be taken again, as in [4, 4]; it never gets an index before i, so every combination is built in one order only, smallest first, and [5, 3] never repeats [3, 5].
  2. All candidates are positive, so left only shrinks: at left = 0 the path is an answer, and a path whose next candidate is bigger than left can never reach it.
  3. After sorting, the first candidate bigger than left means every later one is bigger too, so break cuts the whole rest of the loop instead of checking each.

Complexity

Time O(n^(t / m) × t / m) in the worst case, where t is the target and m the smallest candidate: a path holds at most t / m numbers, each picked from at most n, and each answer is copied. Memory O(t / m) besides the answer: the path and the call stack.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.