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.

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

python

▶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

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.

06

Complexity

Time

O(target * len(nums))

Space

O(target)

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