Collections Hitting a Target Exactly

You are given n numbers and a target. Count how many collections 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. So in the list 5 5, the target 5 is reached in two ways, not one. The empty collection adds up to 0.

## What most people try first

Walking every collection is 2^n, which is about 10^12 at n = 40 and far too slow.

The usual escape from an exponential subset problem is a table indexed by the running total, the way subset-sum is normally taught. That does not work here, and it is worth being precise about why, because the reason is the whole signal for choosing this technique. The table needs one slot per reachable total. The numbers reach 10^9 and there are up to forty of them, so the totals reach 4 * 10^10. No array of that length exists on the machine, and the running time would be proportional to its length. The table is not slow here, it cannot be built at all.

So the item count is small (forty) while the values are huge (10^9). Pay an exponent on the small thing.

## Halve the list

Split into a left half and a right half of about twenty each. Enumerate every total reachable from the left half and every total reachable from the right half. Each is about 2^20, which is a million.

## Why the halves can be counted independently

Every collection of the whole list decomposes into its left part and its right part, and that decomposition is unique: a collection has exactly one left part and exactly one right part. Conversely any left part paired with any right part forms a collection. So the collections are in one-to-one correspondence with the pairs, and counting pairs counts collections, with nothing double counted and nothing missed.

A pair sums to the target exactly when the left total equals target minus the right total. So build a map from left total to HOW MANY left collections reach it, then for each right total r add up the map's entry for target minus r.

## Why a map and not a sorted array

The question asks about one exact value, and a hash map answers "how many reach this value" in a single step without the left totals being sorted at all. A sorted array with two binary searches also works and is what the range version of this question needs, but for an exact target it is strictly more code for the same answer.

## The boundary that breaks a careless implementation

Storing the left totals in a SET rather than a map with counts. A set collapses the two different ways of reaching a total into one, and the answer drops. On the list 5 5 with target 5 a set-based solution reports 1 where the truth is 2. The statement pins positions rather than values precisely so this is a wrong answer and not a matter of taste.

The second is the missing-key path. With large values, target minus r is very often a total the left half cannot reach, so the lookup must contribute 0 rather than whatever a default happens to be.

## Overflow

2^40 is 1099511627776. That is past 2147483647, so the COUNT needs 64 bits, not only the totals. A 32-bit counter wraps silently in C and C++ and reports a plausible wrong number. A list of forty zeros with target 0 is the case that exposes it, because every one of the 2^40 collections qualifies.

## Cost

2^(n/2) to build the map, 2^(n/2) lookups. About two million steps at n = 40, against 10^12.

## Worked example

``` numbers 1 2 3 4 target 10

left half 1 2 totals 0 1 2 3 right half 3 4 totals 0 3 4 7 left counts {0:1, 1:1, 2:1, 3:1}

r = 0 need 10 not in the map adds 0 r = 3 need 7 not in the map adds 0 r = 4 need 6 not in the map adds 0 r = 7 need 3 count 1 adds 1

answer 1 (the collection 1 2 3 4) ```

### Constraints - 1 <= n <= 40 - 0 <= each number <= 10^9 - 0 <= target <= 4 * 10^10 - The answer can reach 2^40, which is about 1.1 * 10^12. Use a 64-bit type for the count as well as for the totals.