Combination Sum IV
Combination Sum IV: count the number of ordered sequences of numbers from nums that sum to target.
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 1000
- All the elements of nums are unique.
- 1 <= target <= 1000
Intuition
Combination sum iv is misleadingly named. Despite the title, it counts permutations — [1, 2] and [2, 1] are counted as two different ways to reach 3. That single fact changes the entire solution, and reading the examples rather than the title is what reveals it.
Because order matters, backtracking is unnecessary. Only the count is required, not the combinations themselves, so this becomes a counting DP:
- dp[t] is the number of ordered ways to reach total t, and dp[t] = sum of dp[t − num] over every number that fits.
The reasoning is direct: any sequence summing to t ends with some number num, and the part before it is a sequence summing to t − num. Adding up over all possible final numbers counts every sequence exactly once.
The base case is dp[0] = 1 — there is exactly one way to reach zero, by choosing nothing. This seeds the entire table.
The loop order is what distinguishes this from a combination count, and it is the whole lesson of the problem:
Putting the target in the outer loop and the numbers in the inner counts permutations, because every number is considered as the final element at every total. Swapping them — numbers outside, target inside — counts combinations instead, which is the Coin Change II pattern.
The two problems differ by nothing more than which loop is outermost. That is worth remembering, since the code looks nearly identical.
The stated follow-up about negative numbers has no finite answer, since negatives allow infinitely long sequences.
Despite the name, combination sum 4 leetcode counts permutations — [1,2] and [2,1] are separate answers. That's why the target loop is outer and the number loop is inner: iterating targets first lets every ordering be built independently.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(target * len(nums)) time and O(target) space.
Read the examples, not the title
Despite its name, this problem counts permutations — [1, 2] and [2, 1] count separately. Recognising this from the examples determines everything that follows.
Count rather than enumerate
Only the number of ways is required, not the sequences themselves, so backtracking is unnecessary. A counting DP is both simpler and far faster.
Define the state
dp[t] is the number of ordered ways to reach total t. Every sequence ends with some number, which is what the transition below exploits.
Set the base case
dp[0] = 1 — exactly one way to reach zero, by choosing nothing. This single value seeds the whole table; setting it to 0 makes every result 0.
Apply the transition
dp[t] = sum of dp[t - num] over every number that fits. Each term counts the sequences ending in that number, so every sequence is counted exactly once.
Put the target in the outer loop
Target outside, numbers inside counts permutations. Swapping the loops counts combinations instead — the Coin Change II pattern. The code looks nearly identical, and this order is the only difference.
Cost of the tabulation
Each of the target states scans every number, giving O(target · n) time and O(target) space for the single array.
Solution & live demo
Common pitfalls
Putting the number loop outside
for num in nums:
for t in range(num, target + 1):
dp[t] += dp[t - num]for t in range(1, target + 1):
for num in nums:Number-outer counts each multiset once regardless of order — that's the combination count, which is a different and smaller answer. The loop order alone decides between combinations and permutations.
Not seeding dp[0]
dp = [0] * (target + 1)
dp[0] = 1
The empty sequence is the one way to reach a target of 0, and every count builds on it. Without the seed the entire table stays zero.
Ignoring overflow on the count
int[] dp = new int[target + 1];
// the problem guarantees the answer fits in a 32-bit int
Intermediate dp values can exceed a signed int even when the final answer fits — LeetCode's constraints permit this, and the accepted solutions rely on the wraparound cancelling out. Worth knowing you're leaning on that rather than assuming the arithmetic is clean.
Edge cases
The inner sum never finds a fitting num for any positive t up to target, so dp[target] = 0.
9 never fits into a target of 3, so the answer is correctly 0.
dp[0] = 1 is the base case; if 0 is queried directly the answer is 1 (the empty sequence).
Exactly one sequence exists for any target: 1 repeated target times.