Учитывая массив различных целых чисел nums и целевое целое число target, верните количество возможных комбинаций, которые в сумме дают target.
Тестовые примеры генерируются таким образом, чтобы ответ помещался в 32-битное целое число.
Решение:
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target+1)
dp[0] = 1
for i in range(1, target+1):
for num in nums:
num_before = i - num
if num_before >= 0:
dp[i] += dp[num_before]
return dp[target]