Why does Combination Sum IV count orders separately?

The problem counts sequences, so (1, 2) and (2, 1) are different. The DP reflects that: it asks which number comes last for every total, so every order is built.

Why is the loop over totals outside the loop over nums?

With totals outside, every num can be the last number of every total, which counts orderings (permutations). Swapping the loops, nums outside and totals inside, counts each combination once regardless of order; that is the Coin Change II recurrence.

What changes if nums can be negative?

With a negative and a positive number, sequences can go up and down forever, so the count can be infinite. The follow-up answer is to cap the sequence length or forbid negatives.

Combination Sum IV

Count the ordered sequences of numbers that add up to a target with a one-dimensional DP over every total.

MediumSolve on LeetCode

Problem Understanding

Combination Sum IV: given an array of distinct positive integers nums and a target, return the number of possible ordered sequences of numbers from nums (each may be used any number of times) that add up to target.

Example: nums = [1, 2, 3], target = 4 returns 7: (1,1,1,1), (1,1,2), (1,2,1), (1,3), (2,1,1), (2,2), (3,1).

Attempt 1: Plain Recursion

count(t) tries every num as the first number and recurses on t - num. It is correct but exponential: count(2) is recomputed inside count(4), count(3) and more. The same totals keep coming back, which is the sign that DP will help.

The Intuition: Which Number Comes Last?

Every sequence that adds up to t ends with some num. Remove that last number and what is left adds up to t - num. So the sequences for t are, for each num <= t, all the sequences for t - num with num appended:

dp[t] = dp[t - nums[0]] + dp[t - nums[1]] + … (only the terms with num <= t)

with dp[0] = 1 for the empty sequence. Each dp[t] only needs smaller totals, so fill the table from 1 up to target.

Interactive Walkthrough

The dp row fills left to right. For the cell being filled, each num is tried as the last number: if it fits, the cell it reaches back to, dp[t - num], is highlighted and added in; if it is larger than t, it is skipped.

Dry Run Table

Input: nums = [1, 2, 3], target = 4

`t`	Last = 1	Last = 2	Last = 3	`dp[t]`
0	—	—	—	1
1	dp[0] = 1	too big	too big	1
2	dp[1] = 1	dp[0] = 1	too big	2
3	dp[2] = 2	dp[1] = 1	dp[0] = 1	4
4	dp[3] = 4	dp[2] = 2	dp[1] = 1	7

The Solution Template

Bottom-up DP over totals, trying every num as the last number.

Combination Sum IV Code

1var combinationSum4 = function(nums, target) {
2    const dp = new Array(target + 1).fill(0);
3    dp[0] = 1;
4    for (let t = 1; t <= target; t++) {
5        for (const num of nums) {
6            if (num <= t) {
7                dp[t] += dp[t - num];
8            }
9        }
10    }
11    return dp[target];
12};

Edge Cases & Common Mistakes

No way to reach the target: nums = [9], target = 3 leaves dp[3] = 0.
Swapping the two loops: nums outside and totals inside counts combinations, not orderings, and returns 4 instead of 7 for the example.
Overflow: some intermediate totals that never feed into dp[target] can exceed 32 bits. The answer itself fits, so the C and C++ versions use unsigned arithmetic, whose wraparound is defined; Java's int also wraps without error.
Forgetting dp[0] = 1: every cell stays 0.

Summary

Combination Sum IV is a 1D DP where each total asks which number comes last: dp[t] adds up dp[t - num] over every num that fits. Loop totals on the outside to count orderings. The table has target + 1 cells and each tries every num: O(target · n) time.

More practice: DSA interview questions with answers · patterns cheat sheet

Maximum Product Subarray

Partition Equal Subset Sum