Combination Sum IV — Solution in Python, Java & C++
Combination Sum IV solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Combination Sum IV is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google, Adobe and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google, Adobe, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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.
Sequences with the same numbers in a different order count as different combinations.
Example 1
Input: nums = [1,2,3], target = 4
Output: 7
Explanation: (1,1,1,1), (1,1,2), (1,2,1), (1,3), (2,1,1), (2,2), (3,1).
Example 2
Input: nums = [9], target = 3
Output: 0
Example 3
Input: nums = [2,3], target = 6
Output: 2
Explanation: 2+2+2 and 3+3.
Constraints
1 <= nums.length <= 121 <= nums[i] <= 100All elements of nums are distinct.1 <= target <= 200The answer fits in a signed 32-bit integer.
Hints for Combination Sum IV
Hint 1
Order matters, so the outer loop must be over the target, with the choice of number inside.
Hint 2
dp[t] = Σ dp[t - num]over everynumthat fits — each term is the count of sequences whose last element isnum.Hint 3
Swapping the loop order would count unordered combinations instead, which is a different problem.
How to solve Combination Sum IV
Order matters, so loop the target outside and the numbers inside: dp[t] = Σ dp[t - num] counts sequences by their last element.
Approach
- Set
dp[0] = 1. - For
tfrom 1 totarget, for eachnum ≤ t,dp[t] += dp[t - num]. - Return
dp[target].
Why it works
Every ordered sequence summing to t ends in some num, and the prefix is an ordered sequence summing to t - num; the sum over num counts each sequence exactly once.
Complexity
- Time —
O(target · n) - Space —
O(target)
Pitfalls
- Swapping the loops counts unordered combinations — the classic Coin Change 2 mistake in reverse.
Reference solution
Python
def combinationSum4(nums, target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1
for t in range(1, target + 1):
for num in nums:
if num <= t:
dp[t] += dp[t - num]
return dp[target]Java
public static int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int t = 1; t <= target; t++) {
for (int num : nums) {
if (num <= t) dp[t] += dp[t - num];
}
}
return dp[target];
}C++
int combinationSum4(vector<int>& nums, int target) {
vector<long long> dp(target + 1, 0);
dp[0] = 1;
for (int t = 1; t <= target; t++) {
for (int num : nums) {
if (num <= t) dp[t] += dp[t - num];
}
}
return (int) dp[target];
}JavaScript
var combinationSum4 = function(nums, target) {
const dp = new Array(target + 1).fill(0);
dp[0] = 1;
for (let t = 1; t <= target; t++) {
for (let i = 0; i < nums.length; i++) {
if (nums[i] <= t) dp[t] += dp[t - nums[i]];
}
}
return dp[target];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming