LeetCode #377 Medium

Combination Sum IV

Count the number of ordered sequences of numbers from nums that sum to target.

dynamic-programmingarray

02

Intuition

The name says 'combination' but this problem counts PERMUTATIONS -- (1,2) and (2,1) are counted as two different sequences, not one. That fact decides the loop order. The target must be the OUTER loop and nums the INNER loop. Swap them -- nums outer, target inner -- and you get the loop order for counting combinations instead, where (1,2) and (2,1) collapse into a single count, silently undercounting the true answer. The fix is to loop target from 1 to the goal, and at each target value, try every number in nums as the possible LAST element of the sequence, adding dp[target - num]. The invariant: dp[t] is the number of ordered sequences summing to t, built by considering every number as a valid final step.

How to spot this pattern

Despite the name this counts permutations — [1,2] and [2,1] are separate answers. That's why the target loop is outer and the number loop is inner: iterating targets first lets every ordering be built independently.

03

Approach

1

Base case

dp[0] = 1 -- there is exactly one way to form the empty sequence summing to zero: use nothing.

2

Target outer, nums inner

For each target value t from 1 up to the goal, sum dp[t - num] over every num in nums that fits (num <= t). Each num represents a distinct choice for the LAST element of a sequence ending at sum t, and different orderings of the same numbers are naturally counted separately because the target advances one step at a time regardless of which number was chosen last.

3

Final answer

dp[target] holds the total count of ordered sequences. Looping nums on the outside would instead fix an order in which numbers become available, collapsing distinct permutations of the same multiset into one.

04

Solution & live demo

▶1class Solution:
▶2    def combinationSum4(self, nums: list[int], target: int) -> int:
▶3        dp = [0] * (target + 1)
▶4        dp[0] = 1
▶5        for t in range(1, target + 1):
▶6            for num in nums:
▶7                if num <= t:
▶8                    dp[t] += dp[t - num]
▶9        return dp[target]

05

Common pitfalls

Putting the number loop outside

✗ Wrong

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

✓ Right

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

Number-outer counts each multiset once regardless of order — that's the combination count, which is a different and smaller answer. The loop order alone decides between combinations and permutations.

Not seeding dp[0]

✗ Wrong

dp = [0] * (target + 1)

✓ Right

dp[0] = 1

The empty sequence is the one way to reach a target of 0, and every count builds on it. Without the seed the entire table stays zero.

Ignoring overflow on the count

✗ Wrong

int[] dp = new int[target + 1];

✓ Right

// the problem guarantees the answer fits in a 32-bit int

Intermediate dp values can exceed a signed int even when the final answer fits — LeetCode's constraints permit this, and the accepted solutions rely on the wraparound cancelling out. Worth knowing you're leaning on that rather than assuming the arithmetic is clean.

06

Edge cases

target is smaller than every num

The inner sum never finds a fitting num for any positive t up to target, so dp[target] = 0.

nums contains a divisor of target that repeats to hit it, e.g. nums=[9], target=3

9 never fits into a target of 3, so the answer is correctly 0.

target = 0

dp[0] = 1 is the base case; if 0 is queried directly the answer is 1 (the empty sequence).

nums has a single 1

Exactly one sequence exists for any target: 1 repeated target times.

07

Complexity

Time

O(target * len(nums))

Space

O(target)

Target-outer, nums-inner loop order is what makes this count permutations rather than combinations.