Pattern visualizer
Combination Sum IV
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. 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..
dp[t] = sum of dp[t - n] over every n
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.
1FUNCTION combinationSum4(nums, target)2 dp[0] <- 13 FOR t <- 1 TO target4 dp[t] <- 05 FOR EACH n IN nums6 IF n <= t7 dp[t] <- dp[t] + dp[t - n]8 RETURN dp[target]
← / → step · space play · Home restart