1228. The Smallest Selection That Adds Up

There are n values, each either 1 or 2, and a target t. Choose a subset whose values add up to exactly t, and report the choice as a string of n characters, 1 where the value is chosen and 0 where it is not. Report the lexicographically smallest such string, or none if there is none.

Since 0 sorts before 1, the smallest string is the one that skips as much as it can as early as it can, which means the chosen values are pushed as far to the RIGHT as possible.

values 1 2 1 2 1, t = 4 -> 00111 the last three add to 1+2+1 = 4 values 1 1 1 1 1 1, t = 3 -> 000111 values 1 1 1 1 1 1, t = 7 -> none

## What most people try first

Every subset, all 2^n of them, keeping the smallest string that hits the target. At n = 1200 that is beyond counting.

The greedy instinct is to skip while you can and take when you must. It is actually right here, and the reason is worth having rather than assuming: a prefix of skips is extendable exactly when the values after it can still reach the target, which is a condition on a sum and is easy to test. The search below tests it, so the search never backtracks, and the greedy rule is what the search does.

## The suffix bound

Let suffix[i] be the total of the values from i onward. At position i with need still required:

• need must not be negative, which is the same as never taking a value larger
• than what is still needed
• need must not exceed suffix[i], since that is the most the rest can give

Both are necessary, and together they are also SUFFICIENT when every value is 1 or 2: any amount from 0 to suffix[i] is reachable from position i except, when all the remaining values are 2, the odd amounts. That exception is why the condition is tested at every step rather than once, and it is why the problem fixes the values to 1 and 2 rather than allowing anything: with arbitrary values the two bounds stop being sufficient and the search genuinely backtracks, which is #1217.

## Why the first complete string is the smallest

The options at each position are tried SKIP first, then TAKE, which is 0 then 1, in increasing character order. So the first complete string found differs from any other at the earliest position where the other took when this one skipped, and 0 sorts before 1.

## Why the reference does not recurse

The search is one decision per position and the input can be 1200 characters long, so a recursion goes 1200 frames deep. Python's default recursion limit is 1000, and raising it does not raise the C stack that CPython actually uses, so a recursive reference crashes here. It is not only Python: a frame holding a few locals is tens of bytes, and at tens of thousands of positions the default thread stack in Java and the main stack in C run out too.

So the reference carries the stack itself. The only thing a recursive frame holds that a loop would lose is WHICH OPTION the frame was about to try next, so that is what the explicit stack stores:

``` nxt[i] = index of the next option to try at position i

i = 0; nxt[0] = 0 while i >= 0: if i == n: a complete string if accepted: answer it and stop i = i - 1 otherwise go back continue if nxt[i] has run past the options at i: i = i - 1 this position is exhausted, go back continue take option nxt[i] and increment nxt[i] <- this is the resume point if the option is refused: continue stay at i, try the next one record it; nxt[i+1] = 0; i = i + 1 descend ```

Three details make or break it. nxt[i] is incremented BEFORE the descent, so coming back to position i continues from the next option rather than repeating the one that just failed, which would loop forever. nxt[i+1] is reset to 0 on every descent, not once at the start, because position i+1 may be entered many times and each entry must start from its first option. And going back is i = i - 1 with no undo of out[i], because out[i] is overwritten before it is ever read again; the carried state lives in stv[i], indexed by position, so it unwinds for free.

## The settled boundaries

A target of 0 gives all zeros. A target above the total of every value is unreachable, so none, and so is a target that no combination of ones and twos can reach, such as an odd target when every value is 2. With every value 1 the answer takes the last t of them, which is a closed form the tests check.

## Cost

O(n) after the bounds, since no step is undone.

Constraints - `1 ≤ n ≤ 1200` - `0 ≤ t ≤ 2400` - every value is `1` or `2`