Combination Sum IV
Problem
nums and a number
target. Count the sequences (numbers may repeat) whose elements add up to
exactly target. Order matters: (1,2) and (2,1) are
counted separately. The answer is guaranteed to fit in a 32-bit integer.nums = [1,2,3], target = 4Output7nums = [9], target = 3Output01 ≤ nums.length ≤ 200 · 1 ≤ nums[i] ≤ 1000, all distinct · 1 ≤ target ≤ 1000 · Follow-up: what changes if negatives are allowed?
Try it yourself
class Solution {
public int combinationSum4(int[] nums, int target) {
}
}
x in nums, and the rest is the same question for
target - x. So ways(t) = Σ ways(t - x) with
ways(0) = 1 — the state is just the remaining sum.Instinct Choose items to hit or stay under a target sum (can it be done, best value, fewest items, how many ways) - index a DP array by the remaining capacity.
Memory hack Once? Walk back. Many? Walk forward. Each item used at most once loops capacity downward; reusable items loop it upward.
Open the Knapsack DP guide →Approaches
Brute ForcePlain Recursion on Remaining Sum
O(nT/m)Space O(T/m)From a remaining sum t, branch on every number that still fits and
add up the counts of the branches. Reaching exactly 0 is one valid
sequence. Each path in the tree is one ordered sequence, so the work is at least the
answer itself (here m = smallest number).
public int combinationSum4(int[] nums, int target) { if (target == 0) return 1; // one way: pick nothing more int count = 0; for (int x : nums) { if (x <= target) count += combinationSum4(nums, target - x); } return count; }
Directly mirrors the definition, but explodes for any sizeable target.
BetterMemoized Recursion (Top-Down)
O(T · n)Space O(T)The recursion only ever asks about remaining sums 0..T, so cache each
result. Each of the T+1 states is solved once by scanning the
n numbers.
public int combinationSum4(int[] nums, int target) { Integer[] memo = new Integer[target + 1]; return ways(nums, target, memo); } private int ways(int[] nums, int t, Integer[] memo) { if (t == 0) return 1; if (memo[t] != null) return memo[t]; int count = 0; for (int x : nums) { if (x <= t) count += ways(nums, t - x, memo); } memo[t] = count; return count; }
Polynomial, but uses recursion depth up to T (risky for big targets).
OptimalBottom-Up DP over Sums
O(T · n)Space O(T)Build dp[t] for t = 1..T in increasing order, so every
dp[t - x] is ready when needed. The outer loop is the sum and the
inner loop is the numbers — that is what makes different orders count
separately.
public int combinationSum4(int[] nums, int target) { int[] dp = new int[target + 1]; dp[0] = 1; // the empty sequence for (int t = 1; t <= target; t++) { for (int x : nums) { if (x <= t) dp[t] += dp[t - x]; } } return dp[target]; }
Dry runnums = [1,2,3], target = 4
- base1····nums=[1,2,3]
- t=111t···dp[0]=1
- t=2112t··dp[1]+dp[0]=2
- t=31124t·2+1+1=4
- t=411247t4+2+1=7 ✔
Same complexity as the memo, iterative and stack-safe.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Plain Recursion on Remaining Sum | O(nT/m) | O(T/m) |
| Better | Memoized Recursion (Top-Down) | O(T · n) | O(T) |
| Optimal | Bottom-Up DP over Sums | O(T · n) | O(T) |
- Putting the
numsloop outside — that counts unordered combinations, not sequences. - Forgetting
dp[0] = 1— every count then stays 0. - Using
-1as an “unset” marker while intermediate sums may overflow; a nullable cache avoids clashes.
- Clarify early that order matters — it decides which loop goes outside.
- Name the state: “number of sequences summing to t”; the transition follows.
- Follow-up: with negatives, cycles like +1/−1 give infinitely many sequences, so a length limit is needed.