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 <= 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?
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(target * numsSize).
Space Complexity: O(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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(target * numsSize).
Space Complexity: O(target).
| Approach | Complexity |
|---|---|
| Dynamic Programming with Memorization | Time Complexity: O(target * numsSize). |
| Dynamic Programming Using Tabulation | Time Complexity: O(target * numsSize). |
Combination Sum IV - Dynamic Programming - Leetcode 377 - Python • NeetCode • 49,625 views views
Watch 9 more video solutions →Practice Combination Sum IV with our built-in code editor and test cases.
Practice on FleetCode