Combination Sum IV solution and explanation
Google
9 more videos on this problem
Combination Sum IV - Dynamic Programming - Leetcode 377 - PythonNeetCode · 11:39 · 57K views
Combination Sum IV | 2 Ways | DRY RUN | Tree Diagram | GOOGLE | SNAPCHAT | META | Leetcode - 377codestorywithMIK · 22:18 · 14K views
Combination Sum IV | Live Coding with Explanation | Leetcode - 377Algorithms Made Easy · 9:52 · 8K views
Letcode 377. Combination Sum Combination Sum IVCode with Alisha · 17:55 · 5K views
Leetcode 377. Combination Sum IV II DP II Top Down II Bottom UpAryan Mittal · 10:08 · 3K views
[Java] Leetcode 377. Combination Sum IV [DP Distinct Ways #4]Eric Programming · 18:37 · 2K views
Leetcode - Combination Sum IV (Python)Timothy H Chang · 6:08 · 2K views
Leetcode 377 Combination Sum IV |DP Basics| Checkout Coding Decoded SDE preparation Sheet link belowCoding Decoded · 10:04 · 2K views
Unlock the Power of Dynamic Programming with LeetCode 377. Combination Sum IV Become a DP WizardvanAmsen · 5:16 · 1K views
Combination Sum IV - LeetCode 377 - Python #dynamicprogramming #leetcode #combinationsum #blind75Deepti Talesra · 12:46 · 1K views
The problem
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.
class Solution:
def combinationSum4(self, nums, target):
memo = [-1] * (target + 1)
memo[0] = 1
def dfs(target):
if target < 0:
return 0
if memo[target] != -1:
return memo[target]
count = 0
for num in nums:
count += dfs(target - num)
memo[target] = count
return count
return dfs(target)
sol = Solution()
print(sol.combinationSum4([1, 2, 3], 4))import java.util.Arrays;
public class Solution {
public int combinationSum4(int[] nums, int target) {
int[] memo = new int[target + 1];
Arrays.fill(memo, -1);
memo[0] = 1;
return dfs(nums, target, memo);
}
private int dfs(int[] nums, int target, int[] memo) {
if (target < 0) return 0;
if (memo[target] != -1) return memo[target];
int count = 0;
for (int num : nums) {
count += dfs(nums, target - num, memo);
}
memo[target] = count;
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 3};
int target = 4;
System.out.println(sol.combinationSum4(nums, target));
}
}#include <vector>
#include <iostream>
class Solution {
public:
int combinationSum4(std::vector<int>& nums, int target) {
std::vector<int> dp(target + 1, -1);
dp[0] = 1;
return helper(nums, target, dp);
}
private:
int helper(const std::vector<int>& nums, int target, std::vector<int>& dp) {
if (target < 0) return 0;
if (dp[target] != -1) return dp[target];
int res = 0;
for (int num : nums) {
res += helper(nums, target - num, dp);
}
dp[target] = res;
return res;
}
};
int main() {
Solution sol;
std::vector<int> nums = {1, 2, 3};
int target = 4;
std::cout << sol.combinationSum4(nums, target) << std::endl;
return 0;
}var combinationSum4 = function(nums, target) {
const memo = Array(target + 1).fill(-1);
memo[0] = 1;
const dfs = (target) => {
if (target < 0) return 0;
if (memo[target] !== -1) return memo[target];
let count = 0;
for (const num of nums) {
count += dfs(target - num);
}
memo[target] = count;
return count;
};
return dfs(target);
};
console.log(combinationSum4([1, 2, 3], 4));#include <stdio.h>
#include <string.h>
int combinationSum4(int* nums, int numsSize, int target) {
int memo[target + 1];
memset(memo, -1, sizeof(memo));
memo[0] = 1; // Base case
int dfs(int remain) {
if (remain < 0) return 0;
if (memo[remain] != -1) return memo[remain];
int count = 0;
for (int i = 0; i < numsSize; i++) {
count += dfs(remain - nums[i]);
}
memo[remain] = count;
return count;
}
return dfs(target);
}
int main() {
int nums[] = {1, 2, 3};
int target = 4;
printf("%d\n", combinationSum4(nums, 3, target));
return 0;
}using System;
public class Solution {
public int CombinationSum4(int[] nums, int target) {
var memo = new int[target + 1];
Array.Fill(memo, -1);
memo[0] = 1;
return Dfs(nums, target, memo);
}
private int Dfs(int[] nums, int target, int[] memo) {
if (target < 0) return 0;
if (memo[target] != -1) return memo[target];
int count = 0;
foreach (var num in nums) {
count += Dfs(nums, target - num, memo);
}
memo[target] = count;
return count;
}
public static void Main(string[] args) {
var sol = new Solution();
Console.WriteLine(sol.CombinationSum4(new[] { 1, 2, 3 }, 4));
}
}The Python solution uses a recursive bottom-up approach with memoization to store previously computed results, allowing it to find the valid combinations efficiently.
Time Complexity: O(target * len(nums)).
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.
class Solution:
def combinationSum4(self, nums, target):
dp = [0] * (target + 1)
dp[0] = 1
for i in range(1, target + 1):
for num in nums:
if i - num >= 0:
dp[i] += dp[i - num]
return dp[target]
sol = Solution()
print(sol.combinationSum4([1, 2, 3], 4))public 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 >= 0) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 3};
int target = 4;
System.out.println(sol.combinationSum4(nums, target));
}
}#include <vector>
#include <iostream>
class Solution {
public:
int combinationSum4(std::vector<int>& nums, int target) {
std::vector<unsigned int> dp(target + 1, 0);
dp[0] = 1;
for (int i = 1; i <= target; ++i) {
for (const auto& num : nums) {
if (i - num >= 0) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
};
int main() {
Solution sol;
std::vector<int> nums = {1, 2, 3};
int target = 4;
std::cout << sol.combinationSum4(nums, target) << std::endl;
return 0;
}var combinationSum4 = function(nums, target) {
const dp = new Array(target + 1).fill(0);
dp[0] = 1;
for (let i = 1; i <= target; i++) {
for (const num of nums) {
if (i - num >= 0) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
};
console.log(combinationSum4([1, 2, 3], 4));#include <stdio.h>
#include <string.h>
int combinationSum4(int* nums, int numsSize, int target) {
int dp[target + 1];
memset(dp, 0, sizeof(dp));
dp[0] = 1; // Base case
for (int i = 1; i <= target; ++i) {
for (int j = 0; j < numsSize; ++j) {
if (i - nums[j] >= 0) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
int main() {
int nums[] = {1, 2, 3};
int target = 4;
printf("%d\n", combinationSum4(nums, 3, target));
return 0;
}using System;
public 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++) {
foreach (int num in nums) {
if (i - num >= 0) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
public static void Main(string[] args) {
var sol = new Solution();
Console.WriteLine(sol.CombinationSum4(new[] { 1, 2, 3 }, 4));
}
}The Python version initializes the DP array with zero, then iteratively computes the number of ways to form every integer up to target using the numbers present in nums.
Time Complexity: O(target * len(nums)).
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.
function combinationSum4(nums: number[], target: number): number {
const f: number[] = 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];
}func combinationSum4(nums []int, target int) int {
f := make([]int, target+1)
f[0] = 1
for i := 1; i <= target; i++ {
for _, x := range nums {
if i >= x {
f[i] += f[i-x]
}
}
}
return f[target]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Memorization | Time Complexity: O(target * len(nums)). |
| Dynamic Programming Using Tabulation | Time Complexity: O(target * len(nums)). |
| Dynamic Programming | – |
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 |
Frequently asked questions
Is Combination Sum IV easy or hard?
Combination Sum IV is rated Medium difficulty. The challenge is recognizing that order matters, which turns the problem into counting permutations using dynamic programming rather than simple combination counting.
How to solve Combination Sum IV in O(n * target)?
Use a bottom-up dynamic programming table. Create a dp array where dp[i] stores the number of combinations that sum to i. Initialize dp[0] = 1 and for each i from 1 to target, iterate through nums and update dp[i] += dp[i - num] when num <= i. This ensures each state is computed once.
What is the best approach for Combination Sum IV?
Dynamic Programming with tabulation is the most common solution. Define dp[i] as the number of ordered combinations that produce sum i, initialize dp[0] = 1, and build results up to the target. For each value i, iterate through the numbers and add dp[i - num]. This runs in O(n * target) time with O(target) space.
What data structure is used in Combination Sum IV?
The core structure is a one-dimensional dynamic programming array that stores counts of ways to reach each sum. Some implementations also use recursion with a memoization map or array to cache intermediate results.
What is the time complexity of Combination Sum IV?
The optimal dynamic programming solution runs in O(n * target) time where n is the number of integers in the array. Each target value from 1 to target iterates through the entire array. Space complexity is O(target) for the DP array.
Combination Sum IV Python or Java solution approach?
Both Python and Java implementations typically use the same DP logic. Define an array dp of size target + 1, set dp[0] = 1, then iterate from 1 to target and update dp[i] using values from dp[i - num]. The algorithm remains O(n * target) regardless of language.
Is Combination Sum IV asked at Google, Amazon, or Meta?
Combination Sum style problems appear frequently in interviews at companies like Amazon, Google, and Meta because they test dynamic programming and recurrence thinking. Variations may ask for combinations, permutations, or constraints on reuse of elements.