Combination Sum IV (LeetCode 377): Count All Ordered Combinations
Given an array of distinct positive integers and a target, how many different ordered sequences of those integers add up to the target?
This is LeetCode 377: Combination Sum IV, and the name can be confusing. Despite sharing a name with Combination Sum and Combination Sum II, this problem is fundamentally different. Those two ask you to find all unordered combinations where order does not matter. This one asks you to count ordered sequences where [1, 1, 2] and [1, 2, 1] and [2, 1, 1] are all counted separately. Mathematically, those are permutations, not combinations. But the name stuck.
The change from "unordered" to "ordered" turns a backtracking problem into a DP problem. You no longer care which specific sequences exist, just how many there are. That counting structure is exactly what DP handles well.
nums = [1, 2, 3], target = 4
The approach
Think of dp[i] as the number of ordered ways to reach sum i using numbers from the input array (with unlimited reuse, any number of times).
The recurrence is clean: for each amount i, look at every number num in the array. If num is at most i, then any sequence that sums to i - num can be extended by placing num at the end, giving a valid sequence that sums to i. So dp[i] += dp[i - num].
The key difference from Coin Change is the loop order. In Coin Change, you iterate coins in the outer loop and amounts in the inner loop, which counts unordered combinations. Here you flip it: amounts in the outer loop, nums in the inner loop. That flip is what makes order matter. For each target amount, you consider every possible last element, not every possible next element. Every distinct last element produces a distinct ordering.
The base case: dp[0] = 1. There is exactly one way to reach sum 0 using no elements at all. This seeds the rest of the table.
The solution
def combinationSum4(nums, target):
dp = [0] * (target + 1)
dp[0] = 1
for i in range(1, target + 1):
for num in nums:
if i >= num:
dp[i] += dp[i - num]
return dp[target]
The outer loop walks from 1 to target. For each amount i, the inner loop tries every number in nums. If num fits (does not exceed i), we add dp[i - num] to dp[i]. We return dp[target] at the end.
That is the entire solution. Two nested loops, a 1D array, and a single base case.
Base case: dp[0] = 1. There is exactly one way to make sum 0: use no numbers.
dp[0] = 1 (by definition)
For sum 1, try each num in [1, 2, 3]. Only num=1 fits (1 <= 1).
dp[1] = 1 = 1
For sum 2, num=1 and num=2 both fit.
dp[2] = 1 + 1 = 2
For sum 3, all three nums fit.
dp[3] = 2 + 1 + 1 = 4
For sum 4, all three nums fit. This is our answer.
dp[4] = 4 + 2 + 1 = 7
Complexity
| Aspect | Complexity |
|---|---|
| Time | O(target * len(nums)) |
| Space | O(target) |
The outer loop runs target times. The inner loop runs len(nums) times per outer iteration. The DP array has target + 1 entries. No recursion, no extra data structures.
The building blocks
This problem sits in the same family as Coin Change, but with a different goal. Both are unbounded knapsack-style problems where you can use each element an unlimited number of times. The difference is what you are optimizing:
- Coin Change minimizes the count of elements used. Loop coins outer, amounts inner.
- Combination Sum IV counts ordered sequences. Loop amounts outer, nums inner.
That loop order swap is the entire mechanical difference. Once you see it, you can reconstruct either solution from the other.
Why does loop order control whether order matters?
When you loop coins in the outer loop and amounts in the inner loop (Coin Change style), you are effectively saying "process all ways to use coin X before moving to coin Y." That ensures each combination is counted in only one canonical order. When you loop amounts in the outer loop and nums in the inner loop (Combination Sum IV style), you consider all nums at every amount independently. Nothing prevents you from reaching the same amount via different orderings, so they all get counted.
This same "loop amounts outer" structure is the correct choice whenever the problem counts ordered sequences from an unbounded set.
Edge cases
target = 0:dp[0] = 1by convention. The one "way" to make sum 0 is the empty sequence. LeetCode treats this as 1.- All nums larger than target: Every
numin the array fails theif i >= numcheck for everyifrom 1 totarget. The entire table stays at 0 except fordp[0]. You return 0. - Single num that divides target evenly: The only valid sequence is that num repeated
target / numtimes. The DP naturally computes this as 1. - Large values: LeetCode 377 notes that the answer may overflow a 32-bit integer. In Python this is not an issue, but in Java or C++ you would need to handle overflow by clamping or checking intermediate values.
From understanding to recall
You can follow the DP table fill step by step right now. The question is whether you can write this from scratch in an interview, without notes, after two weeks have passed.
The detail that trips people up is the loop order. When you are under pressure, "amounts outer, nums inner" might not feel obvious. You might default to coins-outer-amounts-inner without thinking, and produce the wrong answer for ordered counting. Spaced repetition builds the habit of pausing and asking, "does order matter here?" before writing the loops.
The unbounded knapsack pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling it in isolation with spaced repetition, until the loop order question becomes automatic, is much more effective than re-reading explanations every time.
Related posts
- Combination Sum - Backtracking to find all unordered combinations that sum to a target with unlimited reuse. Compare the two to see how "count ordered" versus "enumerate unordered" changes the entire approach.
- Coin Change - The unbounded knapsack sibling problem. Minimizes count instead of counting ordered sequences. Side-by-side comparison of loop orders is the clearest way to understand why they differ.
- Combination Sum II - Each element can only be used once and duplicates must be avoided. Same backtracking skeleton as Combination Sum with tighter constraints.
Practice makes it automatic
If you can read this post and explain every line, that is a great start. The next step is writing the solution cold: close the tab, open a blank editor, and reconstruct combinationSum4 from memory. The first time it takes a few minutes and you might mix up the loop order. After three or four spaced reps at increasing intervals, you write it in 30 seconds without thinking.
That gap between "I understand it" and "I can write it instantly" is exactly what CodeBricks targets. Each building block gets drilled until it is automatic.