Exactly k Numbers Nearest a Target
You are given n numbers, a count k and a target. Choose exactly k of the numbers and print the smallest possible gap between their total and the target.
The gap is reported as a non-negative amount, so a total above the target counts the same as one the same distance below. When k is 0 the only choice is the empty one, whose total is 0.
## What most people try first
Enumerate the choices of size k. There are n choose k of them, and at n = 40 with k = 20 that is 137846528820, about 1.4 * 10^11. Hopeless.
The next idea is tempting and wrong: sort the numbers and take the k that sit closest to target divided by k. It often agrees with the answer, which is exactly what makes it dangerous. On 1 2 3 4 5 with k = 2 and target 7 the mean is 3.5, the two nearest it are 3 and 4, and 3 + 4 = 7 is correct.
Now try 16 15 28 with k = 2 and target 43. The mean is 21.5, so the distances are 5.5, 6.5 and 6.5, and the two nearest are 16 and 15, totalling 31 for a gap of 12. But 15 + 28 = 43 exactly, a gap of 0. The heuristic loses by 12 on three numbers.
The reason is worth keeping. It reasons about individual numbers while the constraint is on their SUM, so it has no exchange argument behind it, and nothing stops a pair of extremes from beating a pair of middles. Sorting does not rescue a sum. That input is a declared test below.
A table indexed by the total cannot be built either, because the numbers reach 10^9 so the totals reach 4 * 10^10.
## Halve the list, and bucket each half by how many it used
Split into halves of about twenty. Enumerate each half, recording for every choice its total AND how many numbers it used.
Here is the step that matters, and it is the same step any second constraint forces. You cannot sort all the left totals together, because a total on its own no longer tells you whether a pairing is legal: you also need its count. Sorting them together throws that away, and the search then returns a partner using the wrong number of items.
So bucket the left half by count: one sorted list of totals per count. A right choice using c items then looks only in the bucket for k minus c, and inside that bucket every entry uses the same number of items, so the count rule holds by construction and an ordinary nearest-value search over totals is valid again.
## Why it is correct
Every choice of exactly k numbers splits uniquely into a left part and a right part, and their counts add to k just as their totals add. So for a right part of count c the legal left partners are exactly the contents of one bucket, all of them and nothing else. Searching that bucket for the total nearest to target minus the right total therefore considers every legal completion.
## The boundary that breaks a careless implementation
A bucket that does not exist. If the right part already uses more than k numbers then k minus c is negative and there is no bucket, so that right part must be skipped rather than looked up. Equally, the left half holds only about n / 2 items, so a required count larger than that has no bucket either.
Then the usual nearest-value trap: after the binary search, the nearest reachable total can be the entry at the insertion point or the one just before it, and both ends of the array must be guarded. k can also be 0, where the answer is simply the target itself.
## Overflow
Totals reach 4 * 10^10, past the 32-bit signed limit of 2147483647, so the totals, the target and the gap all need 64 bits. The value searched for, target minus the right total, can be NEGATIVE, so the type must be signed as well as wide; in C an unsigned type wraps to an enormous positive value and the search lands at the far end of the array.
## Cost
2^(n/2) to enumerate each half, a sort per bucket, and one search per right choice.
## Worked example
``` numbers 1 2 3 4 5 k = 2 target 7
left half 1 2 buckets by count count 0: 0 count 1: 1 2 count 2: 3
right half 3 4 5 choices as (total, count) (0,0) (3,1) (4,1) (5,1) (7,2) (8,2) (9,2) (12,3)
r = (0,0) need count 2 bucket 3 total 3 gap 4 r = (3,1) need count 1 bucket 1 2 want 4, nearest 2 total 5 gap 2 r = (4,1) need count 1 want 3, nearest 2 total 6 gap 1 r = (5,1) need count 1 want 2, nearest 2 total 7 gap 0 r = (7,2) need count 0 bucket 0 total 7 gap 0
answer 0 ```
### Constraints - 1 <= n <= 40 - 0 <= k <= n - 0 <= each number <= 10^9 - 0 <= target <= 4 * 10^10 - Totals reach 4 * 10^10 and the value searched for can be negative, so a signed 64-bit type is required.