· By John Kavanagh

Combination Sum IV: The Order is Part of the Answer

White dominoes form a curved sequence on a dark reflective surface.
Image by Sasun Bughdaryan, licensed from Unsplash.

The title of Combination Sum IV is slightly mischievous. In this problem, 1, 3 and 3, 1 are different answers. If I hear "combinations" and immediately write the coin‑change loops, I've already made the wrong decision before touching the keyboard.

The official problem statement makes the intended meaning clear: different sequences count separately. We have distinct positive input values, may use them repeatedly, and must count ordered sequences adding to a target.

I find the simplest way to reason about it is to ask what the final value of a sequence could be. That question gives us a recurrence, a proof that it doesn't double‑count, and an explanation for why the subtotal loop belongs on the outside.


Classify Answers by Their Last Value

Suppose the allowed values are 1, 3, 4 and the target is five. Every valid sequence ends in one, three, or four. If it ends in one, removing that final value leaves a sequence summing to four. If it ends in three, the remaining sequence sums to two. If it ends in four, it sums to one.

These groups don't overlap because a sequence has only one final value. Within each group, removing the last value is reversible: append that value to any valid smaller sequence and we recover exactly one answer in the group.

Let ways[s] mean the number of ordered sequences summing to s. We can then add ways[s - value] for every allowed value no larger than s.

There is one empty sequence with sum zero, so ways[0] = 1. That base case means a value equal to the current subtotal contributes one single‑element sequence. Setting it to zero would leave every later total at zero, which is consistent but not especially helpful.

All values are positive, so every source subtotal is strictly smaller than its destination. Calculating totals from one upwards therefore makes each dependency available before we need it.


A Small Table with Visibly Ordered Answers

For values 1, 3, 4, the first counts are:

SubtotalEnds in 1Ends in 3Ends in 4Total
11001
21001
31102
42114
54116

The four sequences making four are four ones, one followed by three, three followed by one, and a single four. At subtotal five, appending one to each of those yields four answers. The remaining two are 1,1,3 and 1,4.

Writing out this small set is useful because it lets us inspect what the count means. A numeric table alone can conceal whether we are counting sequences, bags, or a minimum number of items. Six is only a convincing answer when we know which six things it represents.

The last‑value classification also proves completeness. Any valid non‑empty sequence has a permitted final value, and removing it reaches one of the source states included in the recurrence. The groups are disjoint, so adding their sizes neither omits nor duplicates an answer.


Swapping the Loops Changes the State

If we iterate through values first and subtotals second, the table describes answers using only values introduced so far. That is useful for unordered coin combinations because it prevents a bag of values from being introduced in several different orders.

For values 1, 2 and target three, ordered counting returns three: 1,1,1, 1,2, and 2,1. Coin‑first counting returns two because the latter pair describes the same bag.

Neither loop arrangement is inherently superior. They answer different questions. I would keep this three‑versus‑two example beside the implementation because it is small enough to explain in a review and strong enough to catch a plausible refactor.

Reordering the input values themselves should not change the result. The outer subtotal still combines all possible final values. The distinction concerns which dimension gets completed first, not whether the permitted values happen to arrive sorted.


Why I Use Exact Counts Inside the Table

The requested answer is guaranteed to fit a 32‑bit integer. That does not imply that every smaller subtotal has a small count. With only even values and an odd target, the final count is zero, whilst many even subtotals can have enormous numbers of ordered sequences.

For instance, values two and four generate the same recurrence on even totals that steps one and two generate on ordinary staircase heights. An unreachable odd target can therefore sit immediately after a very large reachable count.

I use bigint cells to keep those intermediates exact, then convert the final answer to number under the problem's bound. If I removed that guarantee for a reusable utility, I would return bigint instead of silently converting a potentially huge result.

This example needs an ES2020‑or‑later compilation target and a BigInt‑capable runtime. The TypeScript target setting controls the emitted language level; it doesn't turn arbitrary‑precision arithmetic into ordinary floating‑point operations for old runtimes.


Complete TypeScript Solution

const combinationSum4 = (nums: number[], target: number): number => {
  const ways: bigint[] = Array(target + 1).fill(0n);
  ways[0] = 1n;

  for (let subtotal = 1; subtotal <= target; subtotal += 1) {
    for (const value of nums) {
      if (value <= subtotal) ways[subtotal] += ways[subtotal - value];
    }
  }

  return Number(ways[target]);
};

The table uses O(target + 1) count cells and performs O(nums.length × target) checks and additions. Because the counts are arbitrary‑precision integers, their bit lengths also affect the actual arithmetic cost and storage. The familiar table bounds should not be read as a claim that adding two arbitrarily large numbers is constant‑time.

We don't mutate the input. The stated uniqueness of its values matters: duplicate values would cause the same final‑value group to be counted repeatedly. Sorting can permit an early break in the inner loop, but it isn't necessary for correctness and would need a copy if we wanted to preserve the caller's array.

My Climbing Stairs article is a smaller version of this same ordered‑choice idea. There, the available moves are fixed at one and two. Here, the set of allowed final moves comes from the input.


Negative Values Need a New Question

The follow‑up asks what happens if negative values are allowed. The useful issue is finiteness, not just whether we can index negative array positions.

With values one and minus one, we can reach target one using 1, then 1,-1,1, then 1,-1,1,-1,1, and continue indefinitely. A zero value can create the same problem by being inserted repeatedly without changing a total.

One way to restore a finite question is to impose a maximum sequence length. The state would then need to include how many positions have been used, with reachable sums represented across the required range or in a map. Merely reversing a loop doesn't fix the missing limit.

Positive inputs give this implementation both a finite number of answers and an acyclic dependency order. Those are structural assumptions, not incidental validation details.


Verify the Sequences Independently

For small targets, explicitly enumerate sequences by appending each allowed value until the running sum reaches or exceeds the target. Positivity makes that search finite. Count exact hits and compare them with the table.

Include a target smaller than every available value, a single reusable value, values sharing a divisor that cannot divide the target, and the 1, 2 loop‑order counterexample. Reversing the list of permitted values should preserve every answer. An unreachable odd target with many reachable even subtotals exercises the exact‑count choice.

My state‑selection guide explains why I write down the cell meaning before compressing or rearranging loops. Here the meaning is especially compact: all ordered sequences for one subtotal, classified by their final value. Keeping that sentence beside the code makes it much harder to accidentally turn the answer into a bag of coins.


Planning a platform change?

I help teams make difficult platform work clearer, from architecture decisions and migrations to launch recovery, performance, and search visibility.