LeetCode Solutions
377. Combination Sum IV
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<unsigned long long> dp(target + 1);
dp[0] = 1;
for (int i = 1; i <= target; ++i)
for (const int num : nums)
if (i >= num)
dp[i] += dp[i - num];
return dp[target];
}
};
class Solution {
public int combinationSum4(int[] nums, int target) {
// dp[i] := # of combinations that add up to i
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 0; i <= target; ++i)
for (final int num : nums)
if (i >= num)
dp[i] += dp[i - num];
return dp[target];
}
}
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [1] + [-1] * target
def dfs(target: int) -> int:
if target < 0:
return 0
if dp[target] != -1:
return dp[target]
dp[target] = sum(dfs(target - num) for num in nums)
return dp[target]
return dfs(target)