DSA Tracker

Visualize

Combination Sum IV

dp[t] = sum of dp[t - n] over every n

time O(target * n)space O(target)

Despite the name this is a counting problem, not a search: you never need the sequences themselves, only how many there are. Take any sequence that totals t and look at its LAST number n — chop it off and what remains is a sequence totalling t-n, and every such shorter sequence extends back to exactly one sequence for t. So the count for t is just the sum of the counts for t-1, t-2 and t-3. Because order matters, the target loop is the outer one — swapping the loops would count 1+2 and 2+1 as the same answer, which is the Coin Change II problem instead.

Details

Animated on: nums = [1, 2, 3], target = 7 — count the sequences that add up to 7. Order counts, so 1+2 and 2+1 are two different answers.

Problem:Combination Sum IVMedium

dp[t] = sum of dp[t - n] over every n

step 1 / 10

dp[t] = ordered ways to total t using [1,2,3]

One cell per target sum 0..7. Every cell is unknown so far — dp[t] will hold how many ORDERED sequences of [1,2,3] add up to exactly t.

Pseudocode
1FUNCTION combinationSum4(nums, target)
2  dp[0] <- 1
3  FOR t <- 1 TO target
4    dp[t] <- 0
5    FOR EACH n IN nums
6      IF n <= t
7        dp[t] <- dp[t] + dp[t - n]
8  RETURN dp[target]

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. One cell per target sum 0..7. Every cell is unknown so far — dp[t] will hold how many ORDERED sequences of [1,2,3] add up to exactly t.
  2. Base case dp[0] = 1: there is exactly one way to total 0 — pick nothing. Every later count is ultimately built out of this single 1.
  3. Split every sequence totalling 1 by its LAST number: last=1 leaves 0 ([2,3] are larger than 1, so they cannot be the last pick). So dp[1] = dp[0]=1 = 1.
  4. Split every sequence totalling 2 by its LAST number: last=1 leaves 1, last=2 leaves 0 ([3] is larger than 2, so it cannot be the last pick). So dp[2] = dp[1]=1 + dp[0]=1 = 2.
  5. Split every sequence totalling 3 by its LAST number: last=1 leaves 2, last=2 leaves 1, last=3 leaves 0. So dp[3] = dp[2]=2 + dp[1]=1 + dp[0]=1 = 4.
  6. Split every sequence totalling 4 by its LAST number: last=1 leaves 3, last=2 leaves 2, last=3 leaves 1. So dp[4] = dp[3]=4 + dp[2]=2 + dp[1]=1 = 7.
  7. Split every sequence totalling 5 by its LAST number: last=1 leaves 4, last=2 leaves 3, last=3 leaves 2. So dp[5] = dp[4]=7 + dp[3]=4 + dp[2]=2 = 13.
  8. Split every sequence totalling 6 by its LAST number: last=1 leaves 5, last=2 leaves 4, last=3 leaves 3. So dp[6] = dp[5]=13 + dp[4]=7 + dp[3]=4 = 24.
  9. Split every sequence totalling 7 by its LAST number: last=1 leaves 6, last=2 leaves 5, last=3 leaves 4. So dp[7] = dp[6]=24 + dp[5]=13 + dp[4]=7 = 44.
  10. dp[7] = 44 — the number of ordered sequences from [1,2,3] that sum to 7. Each cell was read, never recomputed, so the whole table costs O(target * 3).

Now solve it yourself

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

Solve Combination Sum IV in the editorAll Dynamic Programming problemsBack to roadmap