Combination Sum IV Python Solution with Tests

lcpy gen -n 377   # by problem number
lcpy gen -s combination_sum_iv   # by problem name

Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.

Input: nums = [9], target = 3
Output: 0

class Solution:
    # Bottom-up DP: dp[t] = number of ways to reach sum t
    # dp[t] = sum(dp[t - num] for num in nums if t >= num), dp[0] = 1
    # Order matters, so iterate target outer, nums inner
    # Time: O(target * n)
    # Space: O(target)
    def combination_sum4(self, nums: list[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        for t in range(1, target + 1):
            for num in nums:
                if t >= num:
                    dp[t] += dp[t - num]
        return dp[target]