Combination Sum IV

Difficulty: Medium Source: NeetCode

Problem

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 fits in a 32-bit integer. Note: the order of numbers in a combination matters — different orderings count as different combinations.

Example 1: Input: nums = [1,2,3], target = 4 Output: 7 (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

Constraints:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• All the integers in nums are unique
• 1 <= target <= 1000

Prerequisites

Before attempting this problem, you should be comfortable with:

• Unbounded Knapsack — using items unlimited times
• Order Matters vs Order Doesn’t Matter — understanding when this gives permutations vs combinations
• DP on a Target Sum — building up from smaller targets

1. Brute Force (Recursion with Memoization)

Intuition

At each step, try placing every number from nums. Sum these choices recursively. Since order matters (1+2 and 2+1 are different), we don’t need to track which numbers have been used — we always start from all numbers again. This is more like counting ordered arrangements (permutations), not combinations.

Algorithm

1. dp(remaining) = number of ways to reach remaining using any numbers in nums.
2. Base case: dp(0) = 1.
3. Recursive case: sum of dp(remaining - num) for all num in nums where num <= remaining.

Solution

def combinationSum4_memo(nums, target):
    memo = {}

    def dp(remaining):
        if remaining == 0:
            return 1
        if remaining in memo:
            return memo[remaining]
        result = 0
        for num in nums:
            if num <= remaining:
                result += dp(remaining - num)
        memo[remaining] = result
        return result

    return dp(target)


print(combinationSum4_memo([1, 2, 3], 4))  # 7
print(combinationSum4_memo([9], 3))         # 0
print(combinationSum4_memo([1, 2, 3], 0))  # 1
print(combinationSum4_memo([3, 1, 2], 35)) # some large number

Complexity

• Time: O(target * len(nums)) — each sub-target computed once
• Space: O(target) — memo table

2. Dynamic Programming (Bottom-Up)

Intuition

dp[i] = number of ordered ways to sum to i. For each target amount i, try every number in nums. If num <= i, then dp[i] += dp[i - num].

The key insight: unlike 0/1 knapsack (where you iterate nums in the outer loop), here you iterate targets in the outer loop and nums in the inner loop. This is what counts ordered permutations — each target amount is reachable from all previous amounts, in any order.

Algorithm

1. Initialize dp = [0] * (target + 1), dp[0] = 1.
2. For each i from 1 to target:
   • For each num in nums:
     • If num <= i: dp[i] += dp[i - num].
3. Return dp[target].

Solution

def combinationSum4(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1  # one way to reach 0: use nothing

    for i in range(1, target + 1):
        for num in nums:
            if num <= i:
                dp[i] += dp[i - num]

    return dp[target]


print(combinationSum4([1, 2, 3], 4))  # 7
print(combinationSum4([9], 3))         # 0
print(combinationSum4([1, 2, 3], 0))  # 1
print(combinationSum4([4, 2, 1], 32)) # large number

Complexity

• Time: O(target * len(nums)) — nested loop
• Space: O(target) — DP array

Common Pitfalls

Confusing this with Combination Sum II (unordered). In Combination Sum II, [1,2] and [2,1] are the same and counted once. Here, order matters — they’re different. The outer-loop-over-targets pattern is what makes this count ordered arrangements.

Wrong loop order for unordered combinations. If you want unordered combinations (where [1,2] == [2,1]), you’d loop over nums in the outer loop. The fact that this problem counts ordered arrangements means target is the outer loop.

Not initializing dp[0] = 1. The empty combination (nothing selected) is the base case that seeds all other counts. Without it, nothing propagates.