2366. Fewest Numbers Reaching a Target

You are given n numbers and a target. Choose as FEW of them as you can so that their total is at least the target, and print how many you chose.

If no collection reaches the target, even taking all of them, print -1.

The empty collection has total 0, so a target of 0 is reached by choosing nothing and the answer is 0.

## What most people try first

Sort the numbers largest first and keep taking until the total reaches the target. That greedy approach is actually correct for this particular question, because every number is non-negative and the constraint is a lower bound: if k numbers can reach the target at all, then the k largest certainly do, since swapping any chosen number for a larger unchosen one never lowers the total. So the smallest workable k is found by taking the largest numbers in order.

That is worth knowing, and it is also worth knowing why this problem is in this topic anyway. The greedy argument above leans on every number being non-negative, which is a property of THIS statement rather than of the shape of the question. Change the numbers to allow negatives, or add a second constraint such as a weight cap, and the exchange argument collapses while the split still works unchanged. So the point here is to build the split on a problem where you can check it against an argument you trust.

A table indexed by the total cannot be built: the numbers reach 10^9 and there are forty of them, so the totals reach 4 * 10^10.

## Halve the list

Split into halves of about twenty. Enumerate each half, recording for every collection its total and how many numbers it uses.

Every collection of the whole list is one left collection plus one right collection, uniquely, so the smallest count overall is the smallest count over such pairs.

## The join runs the other way round

Fix a right collection with total s using c numbers. The left collections that work are those with total at least target minus s, and among those you want the SMALLEST count.

Note which direction the constraint points. Here it is a lower bound on the total, where the previous problems had upper bounds. So sort the left collections by total and sweep from the RIGHT end, turning each count into the smallest count seen at that total or higher. Then binary search for the first position whose total is at least what you still need, and read the swept value there.

## Why it is correct

After the backward sweep, position i holds the smallest count among all left collections of total at least the total at position i. Taking a left collection with a larger total is always allowed when a smaller one suffices, because the constraint is a lower bound, so the swept value at the first position that meets the requirement considers exactly the left collections that meet it.

## The boundary that breaks a careless implementation

When target minus s is zero or negative, every left collection qualifies, including the empty one, and the answer for that right collection is just c. A binary search for a negative value must therefore land at position 0 rather than being clamped away or skipped. Any test where the right half alone already reaches the target exercises this.

The unreachable case is the other one. If the total of all n numbers is below the target then nothing works and the answer is -1, which has to be a deliberate branch rather than a sentinel that leaks out as a huge number.

## Overflow

Totals reach 4 * 10^10, past the 32-bit signed limit of 2147483647, so the target and every total need 64 bits. The COUNT is at most 40, so that fits anywhere.

## Cost

2^(n/2) per half, one sort, one backward sweep, and one binary search per right collection.

## Worked example

``` numbers 1 2 3 4 5 target 11

left half 1 2 collections (total 0, count 0) (1,1) (2,1) (3,2) sorted by total 0:0 1:1 2:1 3:2 smallest count at this total or higher 0 1 1 2

right half 3 4 5 collections (0,0) (3,1) (4,1) (7,2) (5,1) (8,2) (9,2) (12,3)

r = (12,3) need -1 -> position 0, swept 0 count 3 r = (9,2) need 2 -> position of total 2, swept 1 count 3 r = (8,2) need 3 -> position of total 3, swept 2 count 4 r = (7,2) need 4 -> nothing that high, skipped

answer 3 ```

### Constraints - 1 <= n <= 40 - 0 <= each number <= 10^9 - 0 <= target <= 4 * 10^10 - Totals reach 4 * 10^10 and need a 64-bit type. The answer itself is at most 40.