LeetCode 377: Combination Sum IV

Problem Restatement

We are given an array of distinct positive integers nums and an integer target.

We need to count how many possible ordered combinations can add up to target.

Each number in nums can be used multiple times.

Order matters.

That means these are counted as different combinations:

[1, 2, 1]
[2, 1, 1]
[1, 1, 2]

Even though they use the same numbers, their order is different.

Input and Output

Example function shape:

def combinationSum4(nums: list[int], target: int) -> int:
    ...

Examples

Example 1:

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

The possible ordered combinations are:

[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[1, 3]
[2, 1, 1]
[2, 2]
[3, 1]

There are 7 combinations.

So the answer is:

7

Example 2:

nums = [9]
target = 3

The only number is 9, which is already larger than 3.

There is no way to form 3.

So the answer is:

0

First Thought: Backtracking

A direct approach is to try every possible sequence.

At each step, choose one number from nums, subtract it from the remaining target, and continue.

If the remaining target becomes 0, we found one valid sequence.

If it becomes negative, that path fails.

Example:

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

From 4, we may choose 1, 2, or 3.

If we choose 1, the remaining target is 3.

From 3, we again may choose 1, 2, or 3.

This creates a large recursion tree.

Code shape:

class Solution:
    def combinationSum4(self, nums: list[int], target: int) -> int:
        def dfs(remain: int) -> int:
            if remain == 0:
                return 1

            if remain < 0:
                return 0

            total = 0
            for num in nums:
                total += dfs(remain - num)

            return total

        return dfs(target)

This is correct, but it recomputes the same remaining targets many times.

For example, dfs(2) may be reached from several different sequences.

Problem With Brute Force

The brute force recursion branches by every number in nums.

Many paths share the same remaining target.

For example, with:

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

The remaining target 2 can appear after:

[2]
[1, 1]

Both paths ask the same question:

“How many ordered combinations form sum 2?”

This repeated work suggests dynamic programming.

Key Insight

Let:

dp[s]

mean:

the number of ordered combinations that sum to s

We want:

dp[target]

The base case is:

dp[0] = 1

There is exactly one way to form sum 0: choose nothing.

Now consider a target sum s.

To build a sequence that sums to s, choose the last number in the sequence.

If the last number is num, then the previous part must sum to:

s - num

So every combination counted in dp[s - num] can become a combination for s by appending num.

Therefore:

dp[s] += dp[s - num]

for every num where s >= num.

Algorithm

Create an array:

dp = [0] * (target + 1)

Set:

dp[0] = 1

Then compute answers for all sums from 1 to target.

For each sum s:

1. Try every number num in nums.
2. If num <= s, add dp[s - num] into dp[s].
3. After filling the table, return dp[target].

The loop order matters.

We loop over sums first, then numbers:

for s in range(1, target + 1):
    for num in nums:
        ...

This counts ordered combinations.

For example, [1, 3] and [3, 1] are counted separately because they are formed through different last-number choices.

Correctness

We prove that dp[s] stores the number of ordered combinations that sum to s.

The base case is dp[0] = 1. This represents the empty sequence. It is needed so that when s == num, the sequence [num] contributes one valid way.

Now assume all values smaller than s are correct.

For sum s, every valid ordered combination has a last number. Suppose that last number is num.

Then the part before the last number must sum to s - num.

By the assumption, there are exactly dp[s - num] ordered combinations for that previous sum.

Appending num to each of those combinations gives valid ordered combinations for s.

Also, every valid ordered combination for s appears in exactly one group, determined by its last number. So the groups do not overlap.

Therefore summing dp[s - num] over all usable num gives exactly the number of ordered combinations for s.

By induction, dp[target] is correct.

Complexity

Let n = len(nums).

Implementation

class Solution:
    def combinationSum4(self, nums: list[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1

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

        return dp[target]

Code Explanation

We create a DP table:

dp = [0] * (target + 1)

dp[s] means the number of ordered combinations that sum to s.

The base case is:

dp[0] = 1

This means there is one way to form sum 0: use no numbers.

Then we fill the table from smaller sums to larger sums:

for s in range(1, target + 1):

For each sum, we try every possible last number:

for num in nums:

If num can fit inside the current sum:

if num <= s:

then every way to form s - num can be extended by appending num:

dp[s] += dp[s - num]

Finally, the answer is:

return dp[target]

Testing

def test_solution():
    s = Solution()

    assert s.combinationSum4([1, 2, 3], 4) == 7
    assert s.combinationSum4([9], 3) == 0
    assert s.combinationSum4([1], 5) == 1
    assert s.combinationSum4([2], 3) == 0
    assert s.combinationSum4([2, 4, 6], 8) == 7
    assert s.combinationSum4([3, 4, 5], 2) == 0

    print("all tests passed")

test_solution()

Test meaning: