Watch 10 video solutions for Combination Sum IV, a medium level problem involving Array, Dynamic Programming. This walkthrough by CodeHelp - by Babbar has 80,838 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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?
Problem Overview: You are given an array of distinct integers and a target value. The task is to count how many ordered combinations of numbers from the array add up exactly to the target. Order matters: [1,2] and [2,1] are considered different combinations.
Approach 1: Dynamic Programming with Memoization (Top-Down) (Time: O(n * target), Space: O(target))
This approach treats the problem as counting the number of ways to reach a remaining target. Use recursion where each call subtracts a number from nums and continues solving for the smaller target. Without caching, this creates many overlapping subproblems. Memoization stores the result for each remaining target in a map or array so each value is computed once. For every recursive state, iterate through the numbers and accumulate results from target - num. This pattern is common in dynamic programming problems that count permutations of sums.
The key insight: the number of ways to build target equals the sum of ways to build target - num for every number in the array. Memoization avoids recomputing the same states repeatedly, reducing exponential recursion to polynomial time.
Approach 2: Dynamic Programming Using Tabulation (Bottom-Up) (Time: O(n * target), Space: O(target))
Instead of recursion, build the solution iteratively. Create a DP array dp where dp[i] stores the number of combinations that sum to i. Initialize dp[0] = 1 because there is one way to reach zero: choose nothing. Iterate from 1 to target, and for each value iterate through all numbers in the input array. If num <= i, update dp[i] += dp[i - num]. Each entry accumulates combinations formed by appending the current number.
This bottom-up approach avoids recursion overhead and is typically easier to reason about in interviews. The iteration order matters: processing the target values first ensures that permutations are counted correctly. The array itself comes from the array input, while the state transitions reflect classic dynamic programming design.
Recommended for interviews: Interviewers usually expect the bottom-up tabulation solution because it clearly shows the DP state definition and transition rule. The memoized recursion demonstrates the same idea and is useful for explaining the recurrence first. Showing the brute recursive idea, then adding memoization, and finally converting it to tabulation shows strong problem-solving progression.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursion (Brute Force) | O(n^target) | O(target) | Conceptual understanding of the recurrence before optimization |
| Dynamic Programming with Memoization | O(n * target) | O(target) | When solving top-down and avoiding repeated recursive work |
| Dynamic Programming (Tabulation) | O(n * target) | O(target) | Preferred iterative solution for interviews and production code |