Combination Sum IV
MedPrompt
Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.
The test cases are generated so that the answer can fit in a 32-bit integer.
Example 1:
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)
Note that different sequences are counted as different combinations.Example 2:
Input: nums = [9], target = 3
Output: 0
Constraints:
1 <= nums.length <= 2001 <= nums[i] <= 1000- All the elements of
numsare unique. 1 <= target <= 1000
Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a simple recursive function to explore all possible combinations of numbers from the nums array that can sum up to the target. It directly translates the problem's recurrence relation into code.
Algorithm
- Define a recursive function
combinationSum4(nums, target). - Base Case 1: If
target == 0, it means a valid combination is found. Return 1. - Base Case 2: If
target < 0, it's an invalid path. Return 0. - Initialize a counter
count = 0. - Iterate through each number
numin thenumsarray. - For each
num, make a recursive callcombinationSum4(nums, target - num)and add the result tocount. - Return the total
count.
Walkthrough
We define a recursive function, let's call it findCombinations(remainingTarget). The base cases for the recursion are: if remainingTarget is 0, it means we've found a valid combination, so we return 1. If remainingTarget is negative, it's an invalid path, so we return 0. For the recursive step, we iterate through each number num in the nums array. For each num, we make a recursive call with findCombinations(remainingTarget - num). The total number of combinations for remainingTarget is the sum of the results from these recursive calls. This method explores every single possibility, leading to a large number of redundant calculations for the same subproblems (i.e., the same remainingTarget value).
class Solution { public int combinationSum4(int[] nums, int target) { if (target == 0) { return 1; } if (target < 0) { return 0; } int res = 0; for (int i = 0; i < nums.length; i++) { res += combinationSum4(nums, target - nums[i]); } return res; }}Complexity
Time
O(N^T), where N is the number of elements in `nums` and T is the target value. In the worst-case scenario (e.g., `nums` contains 1), the recursion tree can have a depth of T and each node can branch N times. This leads to an exponential number of calls and will likely result in a 'Time Limit Exceeded' error for larger inputs.
Space
O(T), for the recursion stack depth. The maximum depth of the recursion is proportional to the target value T.
Trade-offs
Pros
Simple to understand and implement.
Cons
Extremely inefficient due to re-computing the same subproblems multiple times.
Will not pass for larger test cases due to 'Time Limit Exceeded'.
This approach improves upon the brute-force recursion by using memoization to store the results of subproblems. By caching results, we avoid redundant computations for the same remaining target values.
Algorithm
- Create a memoization array
memoof sizetarget + 1and fill it with a sentinel value (e.g., -1). - Define a helper function
solve(nums, target, memo). - Base Case 1: If
target == 0, return 1. - Base Case 2: If
target < 0, return 0. - Memoization Check: If
memo[target]is not -1, it means the result is already computed. Returnmemo[target]. - Initialize a counter
count = 0. - Iterate through each
numinnums. - Add the result of
solve(nums, target - num, memo)tocount. - Store the result in the memoization table:
memo[target] = count. - Return
count.
Walkthrough
This is a refinement of the recursive approach. We introduce a cache (e.g., an array or a map, often called a memoization table) to store the results for each remainingTarget that has already been computed. We use a memoization array, memo, of size target + 1, initialized with a value like -1 to indicate that a state has not been computed. The recursive function findCombinations(remainingTarget, memo) first checks if the result for remainingTarget is already in our memo table. If it is, we return the stored value immediately. If not, we compute it as in the brute-force approach, and before returning, we store the result in memo[remainingTarget]. This ensures that each subproblem is solved only once.
import java.util.Arrays; class Solution { private int[] memo; public int combinationSum4(int[] nums, int target) { memo = new int[target + 1]; Arrays.fill(memo, -1); return solve(nums, target); } private int solve(int[] nums, int target) { if (target == 0) { return 1; } if (target < 0) { return 0; } if (memo[target] != -1) { return memo[target]; } int res = 0; for (int i = 0; i < nums.length; i++) { res += solve(nums, target - nums[i]); } memo[target] = res; return res; }}Complexity
Time
O(N * T), where N is the number of elements in `nums` and T is the target. Each state from 0 to T is computed only once. For each state, we iterate through the N numbers in `nums`.
Space
O(T), for the recursion stack depth and the memoization array of size `target + 1`.
Trade-offs
Pros
Significantly more efficient than brute-force.
Guaranteed to pass within time limits for the given constraints.
Cons
Has the overhead of recursive function calls.
Can lead to a stack overflow error for very large targets, though not an issue with the given constraints.
This is an iterative approach that builds the solution from the bottom up. It uses an array to store the number of combinations for all sums from 0 to the target, calculating each value based on previously computed smaller values.
Algorithm
- Create a DP array
dpof sizetarget + 1and initialize all elements to 0. - Set the base case:
dp[0] = 1. - Iterate
ifrom 1 totarget(this represents the current sum we are trying to achieve). - Inside this loop, iterate through each
numin thenumsarray. - If the current sum
iis greater than or equal tonum, it means we can formiby addingnumto a combination that sums toi - num. So, we updatedp[i]by addingdp[i - num]to it. - After the loops complete,
dp[target]will hold the total number of combinations. Returndp[target].
Walkthrough
We create a DP array, dp, of size target + 1. dp[i] will store the number of ways to form the sum i. The base case is dp[0] = 1, as there is one way to make a sum of 0 (by choosing no numbers). We then iterate from i = 1 to target. For each i, we calculate dp[i]. The value of dp[i] is the sum of dp[i - num] for every num in nums where i >= num. This is because if we can form a sum i - num, we can add num to it to form the sum i. This is implemented using two nested loops. The outer loop iterates through the targets from 1 to target, and the inner loop iterates through the numbers in nums. The final answer is stored in dp[target].
class Solution { public int combinationSum4(int[] nums, int target) { // dp[i] will store the number of combinations that sum up to i. int[] dp = new int[target + 1]; // There is one way to make sum 0, which is by choosing no elements. dp[0] = 1; // Iterate from 1 to target to fill the dp array. for (int i = 1; i <= target; i++) { // For each target sum i, iterate through the numbers. for (int num : nums) { // If we can form sum i by using num, add the number of ways. if (i - num >= 0) { // Check for potential overflow before adding, though problem statement says it fits in int. if (dp[i] > Integer.MAX_VALUE - dp[i - num]) { // This case might not be hit due to problem constraints but is good practice. } else { dp[i] += dp[i - num]; } } } } return dp[target]; }}Follow-up Discussion: Negative Numbers
If negative numbers were allowed in nums, the problem changes significantly. The current DP approach relies on building solutions for larger targets from smaller ones (dp[i] depends on dp[i-num]). If num is negative, i-num would be greater than i, breaking the bottom-up structure.
More critically, if there's a combination of numbers that sums to zero (e.g., [1, -1]), or even just a single negative number, you could create an infinite number of combinations for a given target (e.g., for target t, you can use (t), (t, 1, -1), (t, 1, -1, 1, -1), etc.).
To make the problem solvable with negative numbers, we would need an additional constraint, such as limiting the maximum number of elements in a combination. Without such a constraint, the number of combinations could be infinite.
Complexity
Time
O(N * T), where N is the number of elements in `nums` and T is the target. This is due to the two nested loops.
Space
O(T), for the DP array of size `target + 1`.
Trade-offs
Pros
Most efficient approach in terms of constant factors as it avoids recursion overhead.
No risk of stack overflow.
Often considered more intuitive for DP problems.
Cons
Slightly less direct translation of the recurrence relation compared to the top-down approach.
Solutions
Solution
public class Solution { public int CombinationSum4 ( int [] nums , int target ) { int [] f = new int [ target + 1 ]; f [ 0 ] = 1 ; for ( int i = 1 ; i <= target ; ++ i ) { foreach ( int x in nums ) { if ( i >= x ) { f [ i ] += f [ i - x ]; } } } return f [ target ]; } }public class Combination_Sum_IV { class Solution { public int combinationSum4 ( int [] nums , int target ) { // dp[i] meaning for value i, how many combination count int [] dp = new int [ target + 1 ]; dp [ 0 ] = 1 ; for ( int targetValue = 1 ; targetValue <= target ; targetValue ++) { for ( int i = 0 ; i < nums . length ; i ++) { if ( nums [ i ] <= targetValue ) { // @note: not dp[targetValue]=dp[targetValue-a]+dp[a] // becasue both will be added in below line for dp[a] and dp[targetValue-a] dp [ targetValue ] += dp [ targetValue - nums [ i ]]; } } } 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 num : nums ) { if ( i >= num ) { dp [ i ] += dp [ i - num ]; } } } return dp [ target ]; } }/** * @param {number[]} nums * @param {number} target * @return {number} */ var combinationSum4 = function (nums, target) { const f = new Array(target + 1).fill(0); f[0] = 1; for (let i = 1; i <= target; ++i) { for (const x of nums) { if (i >= x) { f[i] += f[i - x]; } } } return f[target]; };class Solution {public: int combinationSum4(vector<int> &nums, int target) { int f[target + 1]; memset(f, 0, sizeof(f)); f[0] = 1; for (int i = 1; i <= target; ++i) { for (int x : nums) { if (i >= x && f[i - x] < INT_MAX - f[i]) { f[i] += f[i - x]; } } } return f[target]; }};class Solution: def combinationSum4(self, nums: List[int], target: int) -> int: f = [1] + [0] * target for i in range(1, target + 1): for x in nums: if i >= x: f[i] += f[i - x] return f[target]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.