Combination Sum IV LeetCode 377 — DP Guide

LeetCode 377 Combination Sum IV asks: given an array of distinct positive integers nums and a positive integer target, return the number of possible combinations that add up to target. The problem statement uses the word "combinations," but the twist is that different orderings count as different combinations. So for nums = [1, 2, 3] and target = 4, [1, 1, 2] and [1, 2, 1] and [2, 1, 1] are all counted separately — giving a total of 7.

This is fundamentally a permutation-counting problem despite its name. Each number in nums can be used an unlimited number of times (unbounded), and the order of elements matters. This puts it firmly in the family of unbounded knapsack DP problems, alongside Coin Change (minimize coins) and Coin Change II (count unordered combinations).

The constraints are: 1 ≤ nums.length ≤ 200, 1 ≤ nums[i] ≤ 1000, all elements of nums are unique, 1 ≤ target ≤ 1000. The answer is guaranteed to fit in a 32-bit integer. No negative numbers or zero appear in nums, which simplifies the recurrence significantly.

The most dangerous pitfall in LeetCode 377 is taking the problem name literally. "Combination Sum IV" sounds like it should count unordered combinations, the way Combination Sum I (LeetCode 39) and Combination Sum II (LeetCode 40) do. But the problem statement explicitly says different orderings count as different combinations — so it is really a permutation count, not a combination count.

This distinction has a direct algorithmic consequence. In Coin Change II (LeetCode 518), which counts genuine unordered combinations, you iterate over coins in the outer loop and targets in the inner loop. This ensures each coin ordering is only counted once. In Combination Sum IV, you flip the loops: target is the outer loop and nums is the inner loop. This single loop-order swap is what changes the count from combinations to permutations.

Understanding this trap saves you from implementing the wrong algorithm. If you solve it with Coin Change II loop order, you will get the number of unordered subsets — typically a smaller number. For nums = [1, 2, 3] and target = 4, Coin Change II gives 4 (unordered), while Combination Sum IV gives 7 (ordered). Both are DP on the same 1D array; only the loop order differs.

The top-down recursive solution defines a function count(remaining) that returns the number of ordered sequences summing to remaining. The base case is count(0) = 1: an empty sequence is the one valid way to reach a sum of zero. For any remaining > 0, try each num in nums where num ≤ remaining, and sum up count(remaining - num) over all valid nums. If remaining < 0 we return 0, but since all nums are positive this never happens.

Without memoization, the recursion explores an exponential number of paths. With memoization (a dictionary or array memo of size target + 1), each subproblem count(i) is computed once and cached. The total work is O(target × n) — target distinct subproblems, each requiring O(n) work to iterate over nums.

This memoized recursion is functionally equivalent to the bottom-up DP. Both compute the same dp[i] values. The top-down version is often easier to reason about initially because the base case (target = 0 returns 1) is explicit and the recurrence mirrors the problem definition directly. However, the bottom-up version avoids Python recursion depth limits and is typically preferred in interviews.

The bottom-up DP uses a 1D array dp of size target + 1, initialized to all zeros, with dp[0] = 1. The interpretation is: dp[i] = the number of ordered sequences of nums elements that sum to exactly i. The base case dp[0] = 1 means there is exactly one way to form a sum of zero: the empty sequence.

The recurrence is: for each i from 1 to target, and for each num in nums where num ≤ i, add dp[i - num] to dp[i]. This says: to form an ordered sequence summing to i, take any valid num as the last element and prepend any sequence summing to i - num. Since we iterate over all nums at each target value i, we naturally count every ordering — the sequence ending in 1 then 2, the sequence ending in 2 then 1, etc.

After filling the array from dp[1] to dp[target], the answer is dp[target]. For nums = [1, 2, 3] and target = 4, the dp array builds up as: dp[1]=1, dp[2]=2, dp[3]=4, dp[4]=7. Each step uses previously computed values, making this an efficient one-pass bottom-up computation.

The loop order in the DP is the central insight of this problem family. When you iterate outer=target (i from 1 to target) and inner=nums (each num in nums), you allow every num to be placed at every position relative to all others. At each target sum i, you consider placing each num last — and the count of valid sequences ending in num is dp[i - num]. Summing this over all nums gives dp[i], counting every ordered arrangement.

When you swap to outer=nums and inner=target (as in Coin Change II), you process each coin denomination exhaustively before moving to the next. This means coin 1 is placed before coin 2 in the order of consideration, which prevents counting [2,1] separately from [1,2]. You get the number of multisets (unordered collections) that sum to target — exactly what Coin Change II asks for.

The same 1D dp array, the same recurrence dp[i] += dp[i - num], but a different loop order produces two fundamentally different answers. Outer=target gives permutations (order-sensitive count). Outer=nums gives combinations (order-insensitive count). This is one of the most elegant and memorable insights in DP problem families, and understanding it lets you solve both LeetCode 377 and LeetCode 518 from first principles without memorizing separate algorithms.

Python implementation: initialize dp = [0] * (target + 1) with dp[0] = 1. Then use two nested loops: for i in range(1, target + 1): for num in nums: if i >= num: dp[i] += dp[i - num]. Return dp[target]. This is 5 lines of logic. Time complexity is O(target × len(nums)). Space complexity is O(target) for the 1D dp array.

Java implementation: int[] dp = new int[target + 1]; dp[0] = 1; for (int i = 1; i <= target; i++) { for (int num : nums) { if (i >= num) dp[i] += dp[i - num]; } } return dp[target]; The structure mirrors Python exactly. Both handle the edge case of num > i via the guard condition, ensuring no out-of-bounds access into the dp array.

Edge cases to watch: if target is 0, the answer is 1 (the empty sequence). If no num in nums is ≤ target, the answer is 0 (dp[target] stays 0). The problem guarantees all nums are positive, so num = 0 is never in the input — no infinite loops. The answer fits in a 32-bit integer per constraints, so no overflow handling is needed in most languages.

Combination Sum IV sits at the intersection of two classic problem types. As an unbounded knapsack variant, it connects to Coin Change (LeetCode 322 — minimize number of coins) and Coin Change II (LeetCode 518 — count unordered ways). All three use a 1D dp array of size target + 1 with dp[0] = 1 or 0 as the base case and the same recurrence structure dp[i] += dp[i - num] or dp[i] = min(dp[i], dp[i - num] + 1). The differences lie only in the optimization direction and loop order.

Climbing Stairs (LeetCode 70) is a degenerate case of Combination Sum IV where nums = [1, 2]. The dp recurrence for climbing stairs is dp[i] = dp[i-1] + dp[i-2], which is exactly what the Combination Sum IV algorithm produces when nums = [1, 2]. This makes Combination Sum IV a generalization of Climbing Stairs to arbitrary step sizes. Target Sum (LeetCode 494) is a related permutation-counting problem but with +/- signs on elements, requiring a different DP formulation.

To master this problem family, remember the three variants by their loop structures. Combination Sum IV (permutations): outer=target, inner=nums. Coin Change II (combinations): outer=nums, inner=target. Coin Change (minimum): outer=target, inner=nums with min instead of sum. Recognizing which variant a problem is asking for — and recalling the corresponding loop order — is the skill that makes these problems straightforward in an interview setting.