377. Комбинированная сумма IV [LeetCode]

Учитывая массив различных целых чисел nums и целевое целое число target, верните количество возможных комбинаций, которые в сумме составляют target.

Тестовые примеры генерируются таким образом, чтобы ответ умещался в виде 32-разрядного целого числа.

Пример:

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)

Решение:

С помощью чисел в массиве nums нам нужно создать сумму цели.

Понимание: мы видим, что числа в массиве nums могут повторяться, поэтому нам не нужно отслеживать индекс nums.

Информация о перекрывающихся подзадачах:

Рассмотрим пример, nums = [1,2] и target=2:

Следовательно, результат = 2

Код:

Базовое состояние:

если currentSum превышает цель: возвращает 0

если currentSum равно target: возвращает 1

class Solution {
public:
    
    vector<int> dp;
    int combinationSum4(vector<int>& nums, int target) {
         dp.resize(1001);
        fill(dp.begin(), dp.end(), -1);
        
        return solve(nums, target,0);
    }
    
    int solve(vector<int>& nums, int target, int currSum){
        if(currSum > target) return 0;
        if(currSum == target) return 1;
        if(dp[currSum] != -1) return dp[currSum];
        int ways = 0;
        for(int i=0; i<nums.size(); i++) {
            if(currSum + nums[i] <= target)
                ways += solve(nums, target, currSum + nums[i]);
        }
        return dp[currSum] = ways;
    }
    
};