Skip to main content

377 - Combination Sum IV

Difficulty: Medium | Pattern: Dynamic Programming | Company tags: Amazon, Google, Facebook

Problem Statement​

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

Note: The order of numbers matters — (1,1,2) and (1,2,1) are different combinations.

Example 1:

Input: nums = [1,2,3], target = 4
Output: 7
Explanation: [1,1,1,1],[1,1,2],[1,2,1],[1,3],[2,1,1],[2,2],[3,1]

Example 2:

Input: nums = [9], target = 3
Output: 0

Approach: Bottom-Up DP — O(target × n)​

Key insight: dp[i] = number of ways to reach sum i. For each sum, try every number and add ways of reaching i - num.

Algorithm Flow​

def combinationSum4(nums: list[int], target: int) -> int:
    dp = [0] * (target + 1)
    dp[0] = 1  # one way to reach sum 0 (empty)
    
    for i in range(1, target + 1):
        for num in nums:
            if i >= num:
                dp[i] += dp[i - num]
    
    return dp[target]

Why Order Matters (vs Combination Sum III)​

In standard combination sum (unordered), we loop over items in the outer loop and sums in the inner. Here, order matters so we loop over sums in the outer loop and items in the inner — each sum considers adding any item next.

Dry Run​

nums = [1,2,3], target = 4

idp[i] = sum of dp[i-num] for num in nums
01 (base)
1dp[0] = 1
2dp[1]+dp[0] = 2
3dp[2]+dp[1]+dp[0] = 4
4dp[3]+dp[2]+dp[1] = 7

7 ✓

Edge Cases​

  • No number can reach target → 0
  • nums = [1] → dp[target] = 1 (only one way: all 1s)
  • Large target with many small nums → exponential count, but fits in 32-bit per constraints

Complexity​

  • Time: O(target × n)
  • Space: O(target)

Key Terms​

TermDefinition
Bottom-up DPBuilding the solution iteratively from base cases (dp[0]) up to the target, rather than top-down recursion.
Unbounded knapsack (permutation variant)Each item can be reused unlimited times, and different orderings count as distinct results.
dp[i]Number of ordered combinations of nums that sum exactly to i.
Loop order (sum-outer vs item-outer)Determines whether permutations (order matters) or combinations (order doesn't matter) are counted.

FAQ​

Q: Why does looping sums in the outer loop and items in the inner loop count permutations instead of combinations? A: For each sum i, every number is considered as the last element added, and dp[i-num] already accounts for all orderings that reach i-num. Since every number gets a turn as "last" for every sum, all orderings are counted separately — that's what makes it permutations, not combinations.

Q: How does this differ from Combination Sum III or the classic 0/1 knapsack? A: This problem allows unlimited reuse of each number (unbounded) and counts different orders as different answers (permutations). Combination Sum III fixes the item-outer loop, which prevents reordering and counts combinations instead.

Q: What if nums contains a 0? A: The problem guarantees distinct positive integers, so 0 doesn't occur; if it did, dp[i] += dp[i-0] would create infinite self-reference and needs special handling (usually disallowed by constraints).

Q: How would you solve this recursively with memoization instead of bottom-up? A: Define solve(remaining) returning ways to reach remaining, base case solve(0) = 1, and recurse over nums summing solve(remaining - num) for remaining >= num, memoizing on remaining.

Q: Can the target or numbers be negative? A: No — constraints guarantee positive integers and a non-negative target, which is what allows the strictly increasing dp array approach to terminate.

Quick Revision​

  • Goal: count ordered combinations (permutations) of nums summing to target.
  • dp[i] = number of ways to reach sum i; dp[0] = 1 (empty combination).
  • Outer loop over sums 1..target, inner loop over each number.
  • dp[i] += dp[i - num] whenever i >= num.
  • Sum-outer/item-inner loop order is what makes this count permutations, not combinations.
  • Numbers can be reused any number of times (unbounded).
  • If no combination reaches target, dp[target] = 0.
  • Time: O(target × n), Space: O(target).
  • Contrast with Combination Sum III, which swaps loop order to count combinations only.
  • 322 - Coin Change — same unbounded-DP structure, but minimizes coin count instead of counting ways.
  • 474 - Ones and Zeroes — related knapsack-style counting/optimization DP.
  • Also related in pattern: Combination Sum and Combination Sum II (backtracking variants that enumerate actual combinations rather than counting them), and Coin Change II (counts unordered combinations, contrasting with this problem's ordered permutations).