Combination Sum IV - Solution & Explanation
Problem Statement
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?
Approach Overview
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 1: Dynamic Programming with Memorization
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.
Complexity
Time Complexity: O(target * numsSize).
Space Complexity: O(target).
Approach 2: Dynamic Programming Using Tabulation
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.
Complexity
Time Complexity: O(target * numsSize).
Space Complexity: O(target).
Approach 3: Dynamic Programming
We define f[i] as the number of combinations that sum up to i. Initially, f[0] = 1, and the rest f[i] = 0. The final answer is f[target].
For f[i], we can enumerate each element x in the array. If i \ge x, then f[i] = f[i] + f[i - x].
Finally, return f[target].
The time complexity is O(n times target), and the space complexity is O(target), where n is the length of the array.
Code
Python
Java
C++
Go
TypeScript
JavaScript
C#
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Memorization | Time Complexity: O(target * numsSize). |
| Dynamic Programming Using Tabulation | Time Complexity: O(target * numsSize). |
| Dynamic Programming | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Combination Sum IV - Dynamic Programming - Leetcode 377 - Python • NeetCode • 57,578 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Combination Sum IV easy or hard?
How to solve Combination Sum IV in O(n * target)?
What is the best approach for Combination Sum IV?
What data structure is used in Combination Sum IV?
What is the time complexity of Combination Sum IV?
Combination Sum IV Python or Java solution approach?
Is Combination Sum IV asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Combination Sum IV with our built-in code editor and test cases.
Practice on FleetCode