Dare2Solve
The problem involves calculating the number of possible combinations that add up to a target value using a set of integers. This is a classic dynamic programming problem where the objective is to find the number of ways to achieve a specific target using elements from a given set. Each number from the set can be used as many times as necessary.
The intuition behind solving this problem is to break it down into subproblems. For each target value, we calculate how many combinations can be formed using numbers smaller or equal to that target. If we know the number of ways to form a smaller target, we can add the ways that include the current number to form the larger target. The problem resembles finding permutations rather than combinations since the order of numbers matters.
dp
array of size target + 1
, where dp[i]
stores the number of ways to form the target i
using the available numbers.dp[0] = 1
because there's only one way to get a sum of 0
, which is by using no numbers.1
to target
. For each value, check all available numbers from the input array. If the number can be used (i.e., it is less than or equal to the current target value), then add the number of ways to form the remainder (i - num
) to dp[i]
.dp[target]
, which gives the number of ways to reach the target using the given numbers.O(n * target)
, where n
is the length of the input array. For each target value, we iterate through all numbers in the array.
O(target)
, because we use a dynamic programming array of size target + 1
.
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<long long> dp(target + 1, 0); // Use long long for safety
dp[0] = 1;
for (int i = 1; i <= target; ++i) {
for (int n : nums) {
if (n <= i) {
// Check for potential overflow
if (dp[i] > INT_MAX - dp[i - n]) {
dp[i] = INT_MAX; // Cap the value to INT_MAX
} else {
dp[i] += dp[i - n];
}
}
}
}
return (dp[target] > INT_MAX) ? INT_MAX : (int)dp[target];
}
};
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 n in nums:
if n <= i:
dp[i] += dp[i - n]
return dp[target]
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int n : nums) {
if (n <= i) {
dp[i] += dp[i - n];
}
}
}
return dp[target];
}
}
var combinationSum4 = function (nums, target) {
const dp = new Array(target + 1).fill(0);
dp[0] = 1;
for (let i = 1; i <= target; i++) {
for (const n of nums) {
if (n <= i) {
dp[i] += dp[i - n];
}
}
}
return dp[target];
};