The Smallest Amount You Cannot Make
Given coin values, each usable at most once, print the smallest POSITIVE amount that no subset adds up to.
1 1 3 4 -> 10 every amount 1..9 is makeable, 10 is not
2 3 4 -> 1 1 cannot be made at all
The subset-sum table gives this directly: mark every reachable total, then scan upward
for the first gap. With values up to 10^9 the reachable totals run to 2 * 10^14,
so there is no table to build. The problem has to be solved without one.
## The greedy
Sort the values ascending. Carry res, the smallest amount not yet known to be
makeable, starting at 1. For each value v in order:
if v > res: stop, the answer is res
else: res += v
If the loop finishes, the answer is res.
## Why it works
The invariant is: after processing a prefix of the sorted values, every amount from 1 to
res - 1 is makeable from that prefix, and res is not.
Start: res = 1 and nothing is makeable, so 1..0 is vacuously covered.
Take the next value v.
If v <= res, then the makeable set grows from 1..res-1 to 1..res-1+v. Every
amount x in res..res-1+v can be written as v + (x - v), and x - v lies in
res-v .. res-1, which is within the already-covered range 0..res-1 precisely because
v <= res. So res becomes res + v.
If v > res, then v and everything after it, being sorted, is strictly larger than
res. So no remaining value can help make res, and since the prefix could not make it
either, res is the answer.
The sort is what makes the second branch a proof rather than a guess. Without it a small value could still be waiting later.
## Why the condition is v > res and not v > res + 1
A common slip is v > res + 1, which permits a value exactly one above the frontier and
then wrongly claims res is covered.
1 3 answers 2. After the 1, res = 2. The next value is 3, and 3 > 2, so the
answer is 2. With the wrong test, 3 > 3 is false, res becomes 5, and the answer
comes out as 5, which is wrong because 2 genuinely cannot be made.
## Boundaries
2 3 4 answers 1: no coin is 1, the first value already exceeds res = 1, and the loop
stops immediately.
1 2 4 8 answers 16, the sum plus one, because powers of two make every amount below
their total. That is the case where the loop runs to completion, and a solution that only
ever returns inside the loop fails it.
The answer reaches sum + 1, which at the bounds is about 2 * 10^14, so use 64
bits.