1174. Ordered Sums Reaching a Target

Given n distinct positive values, reusable without limit, and a target t, print every ORDERED sequence of them that totals t. Here the order matters, so 1 2 and 2 1 are two different answers.

2 4 1 2 -> 1 1 1 1 1 1 2 1 2 1 2 1 1 2 2

Compare problem 1168, which asks the same question about combinations and answers 1 1 1 1, 1 1 2, 2 2: three lines instead of five, because the three orderings of one 2 and two 1s are one combination.

## What most people try first

Reach for the 1168 search, which keeps an index i and never looks at a value before it. That index is exactly what makes a combination appear once, so it is exactly what has to go. Removing it is the whole change:

go(rem): if rem == 0: record cur; return for j in 0 .. n-1: # every value, every time if a[j] > rem: break cur.push(a[j]); go(rem - a[j]); cur.pop()

The other common mistake is the reverse: to assume the answer is the combinations multiplied by their orderings, and compute it that way. The counts agree, but the LINES are then produced grouped by combination, which is not the order asked for, and the multiplicity argument needs the multiset coefficient rather than a plain factorial.

## Why it is correct

Every ordered sum with total t is a sequence of values, and the search places any value at any position provided it still fits. So the sequence is reached by choosing its values in order. It is reached once, because two different sequences first differ at some position and took different branches of the same loop there. Trying the values in sorted order makes the sequences come out in the required order directly.

The break cuts nothing: the values are sorted and positive, so once a[j] exceeds rem, no later value fits either.

## Where this problem comes up

It is the difference between "how many ways can I pay 4 using coins of 1 and 2" and "how many ways can I climb 4 steps taking 1 or 2 at a time". The first is a combination question with 3 answers, the second an ordered one with 5. Getting the loop nesting round the wrong way in the dynamic programming version of coin change answers the other question, which is the single most common error in that problem, and seeing both enumerations side by side is the point of this one.

## The output convention, shared by every problem in this block

Each combination is printed on its own line with single spaces between its values. Two combinations are compared position by position NUMERICALLY, and when one is a prefix of the other the shorter comes first. If no combination reaches the target, print none.

## Cost

Proportional to the number of ordered sums times O(t) to print each. That count grows much faster than the combination count: for values 1 2 it is the Fibonacci sequence, 1597 at t = 16, against 9 combinations.

## Overflow

Nothing here overflows, since t is at most 15 and the printed values are at most 100. The COUNT of ordered sums is what grows, and this problem prints the sequences rather than counting them, so the growth shows up as output size rather than as arithmetic.

Constraints - `1 ≤ n ≤ 8` - `1 ≤ t ≤ 15` - `1 ≤ a[i] ≤ 100` - All values are distinct. - It is guaranteed that at most 300 ordered sequences total `t`.