#377 Combination Sum IV
the problem
In plain words
Given distinct positive integers nums and a target, count the sequences of numbers from nums (each may repeat) that add up to target. Different orders count as different sequences: 1+2 and 2+1 are two answers. The name says "combination", but it really counts orderings.
in nums = [1,2,3], target = 4
out 7
1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1.
in nums = [9], target = 3
out 0
- 1 ≤ nums.length ≤ 200
- 1 ≤ nums[i] ≤ 1000, all distinct
- 1 ≤ target ≤ 1000
- The answer fits in a 32-bit int
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternUnbounded knapsack
Every sequence has a last number x, and before it comes any sequence that sums to t − x. So count(t) = Σ count(t − x) over x ≤ t. Filling t from 1 upward and trying every x as the last number counts every order — that's why the target loop goes outside.
solutions
From brute force to optimal
count(t) = Σ count(t − x) for every x ≤ t; count(0) = 1.
- t = 0 → 1 (the empty sequence).
- Try every number as the last one and add up the counts.
k branches per call, depth up to T/m (m = smallest number) — exponential.
Recursion depth.
class Solution { public int combinationSum4(int[] nums, int target) { if (target == 0) return 1; // one sequence makes 0: the empty one int count = 0; for (int x : nums) { if (x <= target) count += combinationSum4(nums, target - x); // x is the LAST number } return count; }}count(t) depends only on t — at most T + 1 states.
- memo filled with −1 (0 sequences is a real answer).
- Check, compute, store.
T states, each loops over k numbers once.
Memo + recursion depth up to T.
class Solution { public int combinationSum4(int[] nums, int target) { int[] memo = new int[target + 1]; Arrays.fill(memo, -1); // -1 = not computed (0 sequences is a real answer) return count(nums, target, memo); } private int count(int[] nums, int t, int[] memo) { if (t == 0) return 1; if (memo[t] != -1) return memo[t]; int total = 0; for (int x : nums) { if (x <= t) total += count(nums, t - x, memo); } return memo[t] = total; }}dp[t] = number of ordered sequences that sum to t.
- dp[0] = 1.
- For t = 1..target: for each x ≤ t: dp[t] += dp[t − x].
- Return dp[target].
Two nested loops: targets × numbers.
One array of T + 1 ints; no stack.
class Solution { public int combinationSum4(int[] nums, int target) { int[] dp = new int[target + 1]; // dp[t] = ordered sequences that add up to t dp[0] = 1; for (int t = 1; t <= target; t++) { // amount OUTSIDE → every order is counted for (int x : nums) { // try every number as the LAST one if (x <= t) dp[t] += dp[t - x]; } } return dp[target]; }}in the room
How to say it in the interview
talk track
- Point at the example first: 1+3 and 3+1 both count, so this counts orderings, not combinations.
- "count(t) = sum of count(t − x)" — then fill t from 1 to target.
- Contrast with Coin Change II: there the coin loop is outside, so each multiset is counted once.
traps
- Putting the numbers loop outside (Coin Change II's order) counts each multiset once → answer too small.
- dp[0] = 1, not 0: the empty sequence is what every sequence grows from.
- Some dp[t] for t < target can exceed an int even when the final answer fits (e.g. every number even, target odd → answer 0). Java's int addition wraps silently and the DP only adds, so the final value is still exact — but never compare or min/max such wrapped values.
what they ask next
Follow-ups
What if nums may contain negative numbers?
Then 1 + (−1) + 1 + (−1) … can go on forever, giving infinitely many sequences. You'd have to cap the sequence length and add it to the state.
Combinations instead of orderings?
That's Coin Change II: numbers loop outside, target loop inside.
before you submit
Edge cases to test
- No number fits: [9], target 3 → 0.
- [1,2], target 3 → 3 (1+1+1, 1+2, 2+1): orders count.
- Unreachable target: [3,5], target 7 → 0.
practise next
Similar problems
- #518Coin Change IIMediumin Dynamic Programming
- #70Climbing StairsEasyin Dynamic Programming
- #39Combination SumMediumin Backtracking