
Description
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.
Intuition
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.
Approach
- Dynamic Programming Array: Create a
dp
array of sizetarget + 1
, wheredp[i]
stores the number of ways to form the targeti
using the available numbers. - Initialization: Initialize
dp[0] = 1
because there's only one way to get a sum of0
, which is by using no numbers. - Filling the DP Array: Loop through all possible target values from
1
totarget
. 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
) todp[i]
. - Return the Result: The final result will be stored in
dp[target]
, which gives the number of ways to reach the target using the given numbers.
Complexity
Time Complexity:
O(n * target)
, where n
is the length of the input array. For each target value, we iterate through all numbers in the array.
Space Complexity:
O(target)
, because we use a dynamic programming array of size target + 1
.
Code
C++
class Solution {
public:
int combinationSum4(vector& nums, int target) {
vector 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];
}
};
Python
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]
Java
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];
}
}
JavaScript
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];
};