377. Combination Sum IV

Problem

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

https://leetcode.com/problems/combination-sum-iv/

Example 1:

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.

Example 2:

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

Constraints:

1 <= nums.length <= 200
1 <= nums[i] <= 1000
All the elements of nums are unique.
1 <= target <= 1000

Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?

Test Cases

1 2	class Solution: def combinationSum4(self, nums: List[int], target: int) -> int:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('nums, target, expected', [
    ([1,2,3], 4, 7),
    ([9], 3, 0),
])
class Test:
    def test_solution(self, nums, target, expected):
        sol = Solution()
        assert sol.combinationSum4(nums, target) == expected

Thoughts

相当于 322. Coin Change 的进阶版，从找到最少的硬币数量，改为找出所有可能的方案总数。

对于一个整数 t，记能组合出 t 的方法总数为 cw(t)。显然有：

cw(t)=\begin{cases} 1 & \text{if }t=0 \\ 0 & \text{if }0<t<\min\{nums\} \\ \sum_i\{cw(a-nums[i])\mid nums[i]\le t\} & \text{otherwise} \\ \end{cases}

跟 problem 322 几乎一模一样，只是把初始值 1 改成 0，无解值 $\infty$ 改成 0，1 + min 改成 sum。

代码也直接照搬过来改一下。

时间复杂度是 O(target * n)，空间复杂度是 O(target)。

Code

solution.py

class ForgetfulList:
    def __init__(self, limit: int, default: int = None, cnt: int = 0):
        """Inits a forgetful list which can remember at most `limit` recent values.
        The first `cnt` values will be set to `default`.
        """
        self._limit = limit
        self._buffer = [default] * limit
        self._pos = cnt % self._limit

    def __getitem__(self, idx: int) -> int:
        return self._buffer[idx % self._limit]

    def __setitem__(self, idx: int, val: int):
        self._buffer[idx % self._limit] = val

    def append(self, val: int):
        self._buffer[self._pos] = val
        self._pos = (self._pos + 1) % self._limit


class Solution:
    def combinationSum4(self, nums: list[int], target: int) -> int:
        nums = [val for val in nums if val <= target]
        if not nums:
            return 0

        min_val = min(nums)
        max_val = max(nums)
        cw = ForgetfulList(max_val, 0, min_val)
        cw[0] = 1
        for amt in range(min_val, target + 1):
            cw.append(sum(cw[amt - val] for val in nums if amt >= val))

        return cw[target]