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] <= 1000nums are unique.1 <= target <= 1000Follow 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?
Combination Sum IV asks you to count the number of possible combinations of numbers from an array that add up to a given target. Unlike similar problems, order matters, meaning sequences like [1,2] and [2,1] are considered different.
A common approach is Dynamic Programming. We build a DP array dp[i] that represents the number of ways to form the sum i. For each value from 1 to target, we iterate through the numbers in the input array and update the count if the number can contribute to the current sum. This effectively builds solutions for larger targets using previously computed smaller results.
This bottom-up DP strategy efficiently avoids recomputation and captures all ordered combinations. The approach runs in O(n × target) time, where n is the number of elements in the array, and uses O(target) space for the DP table.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (Bottom-Up) | O(n × target) | O(target) |
| Top-Down DP with Memoization | O(n × target) | O(target) |
NeetCode
This approach involves creating a recursive solution while storing intermediate results in a memoization array to avoid redundant calculations. Define a recursive function that calculates the number of ways to reach the target from the given list, and store the results of subproblems.
Time Complexity: O(target * numsSize).
Space Complexity: O(target).
1#include <stdio.h>
2#include <string.h>
3
4int combinationSum4(int* nums, int numsSize, int target) {
5 int memo[target + 1];
6 memset(memo, -1, sizeof(memo));
7 memo[0] = 1; // Base case
8
9 int dfs(int remain) {
10 if (remain < 0) return 0;
11 if (memo[remain] != -1) return memo[remain];
12
13 int count = 0;
14 for (int i = 0; i < numsSize; i++) {
15 count += dfs(remain - nums[i]);
16 }
17
18 memo[remain] = count;
19 return count;
20 }
21
22 return dfs(target);
23}
24
25int main() {
26 int nums[] = {1, 2, 3};
27 int target = 4;
28 printf("%d\n", combinationSum4(nums, 3, target));
29 return 0;
30}This C solution uses a memoization technique to store results of subproblems in an array called memo. The main idea is to recursively explore all numbers in the array, and try to put each one into the combination until reaching the target.
In this method, an iterative bottom-up approach is used. A DP array is created where each index represents the number of ways to sum to that index using numbers from nums. We incrementally build solutions from smaller subproblems to solve for larger targets.
Time Complexity: O(target * numsSize).
Space Complexity: O(target).
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
In this problem, combinations are treated as sequences. That means [1,2] and [2,1] are considered different results, which increases the total count and affects how the dynamic programming state is built.
Yes, variations of Combination Sum problems frequently appear in technical interviews at major tech companies. They test understanding of dynamic programming, recursion, and counting permutations with constraints.
The optimal approach uses dynamic programming. We maintain a DP array where each index represents the number of ways to build that sum. By iterating through all numbers for each target value, we count ordered combinations efficiently.
A one-dimensional dynamic programming array is typically used. It stores the number of ways to reach each intermediate sum from 0 to the target, allowing previously computed results to build larger sums efficiently.
This C implementation uses a DP array where each element at index i stores the number of ways to form the sum i, iterating through each number in nums to update the array.