377. Combination Sum IV

Problem¶

Count the ordered sequences of values from nums that sum to target. Values may be reused.

For nums = [1, 2] and target = 3, the answer is 3: (1, 1, 1), (1, 2), and (2, 1).

Key trick¶

Let dp[total] count sequences summing to total. For each total, try every value as the last element of a sequence.

Trap¶

Loop over totals first, then values. Reversing the loops counts unordered combinations instead. Set dp[0] = 1 so a value equal to the current total contributes one sequence.

With negative values, sequences can contain repeatable zero-sum cycles, making the count infinite. A maximum sequence length would make the follow-up finite.

Why is it interesting?¶

The loop order changes what the dynamic program counts, even though the recurrence looks similar.

Python solution¶

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

        for total in range(1, target + 1):
            # Choose the last value of each ordered sequence.
            for x in nums:
                if x <= total:
                    dp[total] += dp[total - x]

        return dp[target]

Time: \(O(n \cdot \text{target})\). Space: \(O(\text{target})\).

Comment on my solution¶

Not provided.