2367. Collections of a Given Size Hitting a Target

You are given n numbers, a size k and a target. Count how many collections of EXACTLY k of those numbers add up to exactly the target, and print the count.

Two collections are different if they use a different set of positions, even when the values at those positions are equal. When k is 0 the only collection of that size is the empty one, whose total is 0.

## What most people try first

Enumerate every collection of size k. There are n choose k of them, and at n = 40 with k = 20 that is about 1.4 * 10^11, which is worse than hopeless.

The table route fails too, and it is instructive to see exactly where. A table indexed by (position, total) would work if the totals were small, but the numbers reach 10^9 so the totals reach 4 * 10^10. Adding the size as a second index does not help, because the total was already the index that could not fit.

## Halve the list, and carry two numbers instead of one

Split into halves of about twenty. Enumerate each half, but now record TWO things per collection: its total and how many numbers it uses.

Every collection of the whole list splits uniquely into a left part and a right part, and crucially both the total and the size ADD across that split. A whole collection has total t and size s exactly when its left part has total tl and size sl, its right part has total tr and size sr, and tl + tr = t together with sl + sr = s.

So build a map whose KEY IS THE PAIR (total, size) and whose value is how many left collections have that exact pair. Then for each right collection with total w and size c, the left partners you need are those with the pair (target minus w, k minus c), and the map gives their number in one lookup.

## Why the key must be the pair and not just the total

This is the whole difficulty of the problem, so it is worth stating plainly. If you key only on the total, you count every left collection that reaches the right total regardless of how many numbers it used, and the size constraint silently disappears. The answer then becomes the count of ALL collections hitting the target, which is a different and larger number. Keying on the pair is what enforces both constraints at once, and it costs nothing: the map has the same number of entries either way.

## The boundary that breaks a careless implementation

Negative sizes. If a right collection already uses more than k numbers then k minus c is negative, and no left collection can have a negative size. The lookup must miss rather than being clamped to 0, because clamping to 0 would wrongly count the empty left collection.

And k can equal 0, where the only answer is whether the target is 0. A loop written as "for sizes 1 to k" skips that case entirely.

## Overflow

The count can be as large as 40 choose 20, which is 137846528820. That is past the 32-bit signed limit of 2147483647, so the COUNT needs 64 bits and not only the totals, which themselves reach 4 * 10^10.

## Cost

2^(n/2) to build the map, 2^(n/2) lookups. A few million steps at n = 40, against 1.4 * 10^11 for enumerating the size-k collections.

## Worked example

``` numbers 1 2 3 4 5 k = 2 target 7

left half 1 2 collections as (total, size): (0,0) (1,1) (2,1) (3,2) map: {(0,0):1, (1,1):1, (2,1):1, (3,2):1}

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

r = (0,0) need (7,2) not in the map adds 0 r = (3,1) need (4,1) not in the map adds 0 r = (4,1) need (3,1) not in the map adds 0 <- (3,2) is there, size differs r = (7,2) need (0,0) count 1 adds 1 r = (5,1) need (2,1) count 1 adds 1 r = (8,2) need (-1,0) not in the map adds 0 r = (9,2) need (-2,0) not in the map adds 0 r = (12,3) need (-5,-1) size is negative adds 0

answer 2 (3 and 4, and 2 and 5) ```

### Constraints - 1 <= n <= 40 - 0 <= k <= n - 0 <= each number <= 10^9 - 0 <= target <= 4 * 10^10 - The count reaches 40 choose 20, which is 137846528820, so the count needs a 64-bit type as well as the totals.