LeetCode 377 - Combination Sum IV

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem gives us an array of distinct positive integers called nums and a target integer called target. We must determine how many different ordered sequences of numbers from nums sum exactly to target.

The key detail is that order matters. This makes the problem very different from the classic Combination Sum problems where combinations are considered identical regardless of ordering.

For example, if nums = [1,2,3] and target = 4, the sequences (1,2,1) and (2,1,1) are counted separately because their order differs.

Each number in nums can be used an unlimited number of times. We are not choosing subsets, we are constructing sequences whose total equals the target.

The input constraints are important:

nums.length <= 200
target <= 1000
All numbers are positive
All numbers are distinct

The positivity constraint is especially important because it guarantees progress toward the target. Every time we add a number, the remaining sum decreases. This prevents infinite recursive loops.

The target size of at most 1000 strongly suggests that dynamic programming is feasible. A solution with roughly O(target * len(nums)) complexity is efficient enough.

Several edge cases are important:

If no combination can form the target, the answer should be 0
If a number is larger than the current remaining target, it cannot contribute
Since order matters, we must count permutations separately
Because numbers are positive, recursion naturally terminates
The result fits within a 32-bit integer, so overflow is not a concern in Python, though it is still good to be aware of it in Go

Approaches

Brute Force Approach

A straightforward approach is to recursively try every possible number at every step.

For a remaining target remain, we attempt to subtract every value in nums. Each recursive call explores all possible continuations of the sequence.

For example:

Start with target 4
Choose 1, recurse on 3
Choose 2, recurse on 2
Choose 3, recurse on 1

Whenever the remaining target becomes 0, we found a valid sequence and return 1.

This brute force method is correct because it explores every possible ordered sequence. However, it performs enormous repeated work.

For instance, the number of ways to form target 3 may be computed many times from different recursive paths. As the target grows, the recursion tree expands exponentially.

This leads to extremely poor performance.

Key Insight for Optimization

The critical observation is that the problem contains overlapping subproblems.

The number of ways to form a remaining target x is always the same, regardless of how we reached x.

For example:

Ways to form 3
Ways to form 2
Ways to form 1

These values are repeatedly recomputed in the brute force solution.

This makes the problem ideal for dynamic programming.

We define:

dp[i] = number of ordered combinations that sum to i

To compute dp[i], we try every number in nums:

If num <= i
Then every way to form i - num can be extended by appending num

So:

dp[i] += dp[i - num]

This bottom up dynamic programming approach eliminates repeated computation and efficiently builds the answer from smaller subproblems.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k^target)	O(target)	Explores every recursive sequence, exponential growth
Optimal Dynamic Programming	O(target * n)	O(target)	Reuses previously computed subproblems

Here, n is len(nums) and k represents the branching factor.

Algorithm Walkthrough

Create a DP array of size target + 1.

We use dp[i] to store the number of ordered combinations that sum to i. 2. Initialize the base case.

Set dp[0] = 1.

This represents the empty sequence. There is exactly one way to create sum 0, choose nothing. 3. Iterate through all target values from 1 to target.

We build solutions incrementally from smaller sums to larger sums. 4. For each target value current, try every number in nums.

If num <= current, then num can be the final element of a sequence summing to current. 5. Add the number of ways to form current - num.

Every valid sequence that forms current - num can be extended with num.

Therefore:

dp[current] += dp[current - num] 6. Continue until the entire DP table is filled.

By the time we compute dp[target], all smaller states are already known. 7. Return dp[target].

This contains the total number of ordered combinations.

Why it works

The algorithm works because every ordered sequence ending at sum current must end with some number num from nums.

If we remove that final number, the remaining sequence must sum to current - num.

Since dp[current - num] already stores the number of ways to form that smaller sum, adding all such possibilities across every valid num counts every ordered sequence exactly once.

The bottom up ordering guarantees that when computing dp[current], all required smaller states are already available.

Python Solution

from typing import List

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

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

        return dp[target]

The implementation starts by creating a DP array initialized with zeros. Each index represents a target sum, and the value at that index represents the number of ordered combinations that produce that sum.

The base case dp[0] = 1 is essential. It represents one valid way to produce sum zero, using an empty sequence.

The outer loop iterates from 1 through target, building solutions incrementally. For each current target value, the inner loop checks every number in nums.

Whenever num <= current, the algorithm adds dp[current - num] into dp[current]. This corresponds to extending all sequences that form the smaller sum by appending num.

Finally, the method returns dp[target], which contains the total number of ordered sequences.

Go Solution

func combinationSum4(nums []int, target int) int {
	dp := make([]int, target+1)
	dp[0] = 1

	for current := 1; current <= target; current++ {
		for _, num := range nums {
			if num <= current {
				dp[current] += dp[current-num]
			}
		}
	}

	return dp[target]
}

The Go implementation follows the exact same logic as the Python solution.

The DP array is created using a slice with length target + 1. Go integers are sufficient because the problem guarantees the answer fits within a 32-bit integer.

Unlike Python, Go does not have dynamic list resizing for this use case, so we explicitly allocate the slice size upfront using make.

The iteration structure and recurrence relation remain identical.

Worked Examples

Example 1

Input:

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

Initial DP state:

Index	0	1	2	3	4
dp	1	0	0	0	0

Now compute each target value.

Compute dp[1]

Using 1: dp[1] += dp[0] = 1

Index	0	1	2	3	4
dp	1	1	0	0	0

Compute dp[2]

Using 1: dp[2] += dp[1] = 1
Using 2: dp[2] += dp[0] = 1

Total:

dp[2] = 2

Sequences:

(1,1)
(2)

Index	0	1	2	3	4
dp	1	1	2	0	0

Compute dp[3]

Using 1: dp[3] += dp[2] = 2
Using 2: dp[3] += dp[1] = 1
Using 3: dp[3] += dp[0] = 1

Total:

dp[3] = 4

Sequences:

(1,1,1)
(1,2)
(2,1)
(3)

Index	0	1	2	3	4
dp	1	1	2	4	0

Compute dp[4]

Using 1: dp[4] += dp[3] = 4
Using 2: dp[4] += dp[2] = 2
Using 3: dp[4] += dp[1] = 1

Total:

dp[4] = 7

Final DP table:

Index	0	1	2	3	4
dp	1	1	2	4	7

Answer:

Example 2

Input:

nums = [9]
target = 3

Initial DP:

Index	0	1	2	3
dp	1	0	0	0

Since 9 > current for every value from 1 to 3, no updates occur.

Final DP:

Index	0	1	2	3
dp	1	0	0	0

Answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(target * n)	For each target value, we iterate through all numbers
Space	O(target)	The DP array stores one value for each target sum

The algorithm processes every target value from 1 to target. For each value, it iterates through all elements in nums.

Since there are target states and each state examines n numbers, the total complexity is O(target * n).

The space complexity is linear because we only store the DP array of size target + 1.

Test Cases

solution = Solution()

assert solution.combinationSum4([1, 2, 3], 4) == 7  # provided example
assert solution.combinationSum4([9], 3) == 0  # impossible target
assert solution.combinationSum4([1], 1) == 1  # single exact match
assert solution.combinationSum4([1], 5) == 1  # only one repeated sequence
assert solution.combinationSum4([2], 1) == 0  # number larger than target
assert solution.combinationSum4([1, 2], 3) == 3  # ordered permutations counted
assert solution.combinationSum4([2, 3, 5], 8) == 6  # multiple valid paths
assert solution.combinationSum4([4, 2, 1], 32) > 0  # larger target stress case
assert solution.combinationSum4([3, 4, 5], 2) == 0  # all numbers exceed target
assert solution.combinationSum4([1, 50], 10) == 1  # large unused number

Test	Why
`[1,2,3], target=4`	Validates the main example
`[9], target=3`	Verifies impossible targets return zero
`[1], target=1`	Smallest successful input
`[1], target=5`	Repeated usage of same number
`[2], target=1`	Number larger than target
`[1,2], target=3`	Confirms ordering matters
`[2,3,5], target=8`	Multiple branching combinations
`[4,2,1], target=32`	Larger stress scenario
`[3,4,5], target=2`	No usable numbers
`[1,50], target=10`	Large irrelevant values ignored correctly

Edge Cases

One important edge case occurs when no combination can form the target. For example, nums = [9] and target = 3. A naive recursive implementation might continue exploring useless branches unnecessarily. In the DP solution, states simply remain zero when no valid transitions exist, so the answer correctly becomes 0.

Another important case is when the array contains only one number. For example, nums = [1] and target = 5. There is exactly one sequence: five repetitions of 1. The implementation handles this naturally because each state depends only on the previous one.

A subtle edge case involves ordering. For nums = [1,2] and target = 3, the sequences (1,2) and (2,1) must both be counted separately. This is why the outer loop iterates over target values first and numbers second. Reversing the loop order would instead count unordered combinations.

A final important edge case relates to large target values. Since target can be as large as 1000, an exponential recursive solution would time out. The DP implementation avoids repeated work by storing intermediate results, ensuring efficient execution even for large inputs.

The follow up question about negative numbers is also significant. If negative values are allowed without restriction, infinite combinations become possible. For example, with [1, -1] and target 1, we could endlessly append (1, -1) pairs. To safely allow negative numbers, we would need an additional constraint, such as limiting the maximum sequence length.