In count-the-ways DP with unlimited item types, why does moving the target loop outside change the count?

## Two nestings, one table A plan builder offers add-on data packs in a few fixed sizes, each purchasable any number of times, and you want to know how many ways a customer can assemble exactly a target allowance. The table is an array `ways` indexed by target, with `ways[0] = 1` — there is exactly one way to reach zero, by selecting nothing — and every other cell starting at 0. The update is always `ways[t] = ways[t] + ways[t - size]`. What is *not* fixed is which loop is outside. Both nestings touch the same cells with the same arithmetic. They answer different questions, and the gap between the answers grows fast. ## Item loop outside: unordered selections Process pack sizes one at a time; for each, sweep targets upward and fold that pack into every cell it can reach. When pack `k` is being folded in, the table already reflects exactly the selections buildable from packs `0..k-1`, and after the sweep it reflects selections buildable from packs `0..k`, with any number of copies of pack `k`. The key property is that a selection is only ever built in one canonical order: non-decreasing pack index. There is no moment at which the algorithm can add a 1 GB pack after it has finished with 2 GB packs, because the 1 GB stage is over. So every multiset is counted exactly once. This is the count of **combinations**. ## Target loop outside: ordered sequences Now sweep targets from 1 upward and, at each target, sum over every pack that could have been the last one bought. `ways[t] = sum over sizes s of ways[t - s]`. This is a completely legitimate recurrence — but read what it says. It classifies each way to reach `t` by its final purchase. Two sequences that use the same multiset but end differently are in different classes and are both counted. This is the count of **ordered sequences**, that is, of purchase histories. ## The hand trace that settles it Packs of 1 GB and 2 GB, target 3 GB. Item-outer. After folding in the 1 GB pack: `ways = [1, 1, 1, 1]` — one way to reach each of 0, 1, 2, 3 using only 1 GB packs. Now fold in the 2 GB pack, sweeping targets 2 and 3: `ways[2] += ways[0]` gives 2, `ways[3] += ways[1]` gives 2. Final answer 2: `{1,1,1}` and `{1,2}`. Target-outer. `ways[0] = 1`. `ways[1] = ways[0] = 1`. `ways[2] = ways[1] + ways[0] = 2`. `ways[3] = ways[2] + ways[1] = 3`. Final answer 3: the sequences `1,1,1`, `1,2` and `2,1`. Two lines of code apart, and 2 versus 3. Extend the target and the ordered count grows exponentially while the unordered count grows polynomially in the number of pack types — this is not a rounding difference you can patch up afterwards. ## The mistake to name The misconception to shoot down explicitly is "swapping the two loops is a harmless refactor — the same cells get filled either way". The cells *are* the same. The dependency structure is not. Someone tidying a nested loop for readability, or reordering to hoist a bounds check, can silently change a report's meaning, and nothing crashes. A related error is believing the two counts are related by a simple correction factor — divide by a factorial, say. They are not, because different multisets have different numbers of arrangements depending on how many repeats they contain, so no single factor converts one count into the other. ## When nesting does not matter If the aggregator is a maximum, a minimum, or a boolean OR, the nesting is irrelevant: those aggregators do not distinguish between two paths to the same state, so reachability and optimal totals come out the same either way. Nesting matters exactly when the aggregator **counts distinct constructions**, because then the question of what makes two constructions distinct is being answered implicitly by the loop order. ## What to do in the interview and in the code Say which quantity each nesting computes before you write it, then ask which one is wanted. "Number of ways" is genuinely ambiguous in a requirement, and the ordered reading is sometimes the intended one — a count of purchase histories or of step sequences is a real question. Then protect the choice: a single unit test on a target where the two counts differ (three is enough, with sizes 1 and 2) will fail loudly the day someone swaps the loops. ## Cost Both nestings are O(n * target) time and O(target) space for `n` item types. The counts themselves grow quickly, so the running total is the practical constraint long before the loop is — an ordered count over even a modest target will exceed a fixed-width integer, which is its own review checkpoint.