Collections With a Total in Range
You are given n numbers and two bounds, lo and hi. Count how many collections of those numbers have a total that is at least lo and at most hi, and print the count.
Both bounds are included. Two collections are different if they use a different set of POSITIONS, even when the values are equal. The empty collection has total 0, so it counts whenever lo is 0.
## What most people try first
2^n collections is about 10^12 at n = 40, too slow. And a table indexed by the running total cannot be built, because the numbers reach 10^9 so the totals reach 4 * 10^10, which is far past any array length. When the item count is small and the values are huge, the exponent has to be paid on the items.
If you have already solved the exact-target version of this question, the obvious move is to reuse its hash map and call it once per value in the range. That fails for a reason worth seeing: the range can contain up to 4 * 10^10 distinct values, so looping over the range is worse than looping over the collections.
## Halve the list, then ask a range question
Split into halves of about twenty. Enumerate every left total and sort them. Enumerate every right total.
Fix a right total r. A left total l completes a valid collection exactly when lo is at most l plus r, which is at most hi. Rearranged, that says l lies between lo minus r and hi minus r, both ends included. Since the left totals are sorted, those are a contiguous block, and you only need its SIZE, not its contents.
## Why it is correct
Every collection decomposes uniquely into a left part and a right part, and any left part pairs with any right part to form a collection. So the collections correspond one-to-one with the pairs, and summing the block sizes over all right totals counts each valid collection exactly once.
## Why the container changes from the exact version
A hash map answers "how many reach this one total" in a single step, but it cannot be asked for a range at all, because its keys have no order. A sorted array can, in two binary searches. The question's shape decides the container, and that is the real lesson of this pair of problems.
## The boundary that breaks a careless implementation
Both ends are inclusive, so the two searches are NOT the same search.
The lower end needs the first position at or above lo minus r. Using the "strictly above" search there drops every collection whose total is exactly lo.
The upper end needs the first position strictly above hi minus r. Using "at or above" there drops every collection whose total is exactly hi.
When lo and hi are equal these two errors cancel on some inputs and not on others, which is the worst possible failure mode: the solution passes a few tests and then does not. Write down which search goes at which end before coding them.
Also keep duplicate left totals. Two different position sets that happen to reach the same total are two different collections and must remain two entries in the sorted array.
## Overflow
2^40 is 1099511627776, so the COUNT needs 64 bits and not just the totals. hi reaches 4 * 10^10, so hi minus r needs 64 bits too. Note that 2 * 10^9 still fits in a signed 32-bit integer, since the limit is 2147483647, which is why a small test can pass on a 32-bit build and a large one cannot.
## Cost
2^(n/2) to enumerate each half, one sort, and two binary searches per right total.
## Worked example
``` numbers 1 2 3 4 range 3 to 7
left half 1 2 totals 0 1 2 3 right half 3 4 totals 0 3 4 7 left totals sorted 0 1 2 3
r = 0 want l in [3, 7] block is 3 size 1 r = 3 want l in [0, 4] block is 0 1 2 3 size 4 r = 4 want l in [-1, 3] block is 0 1 2 3 size 4 r = 7 want l in [-4, 0] block is 0 size 1
answer 10 ```
### Constraints - 1 <= n <= 40 - 0 <= each number <= 10^9 - 0 <= lo <= hi <= 4 * 10^10 - The answer can reach 2^40. Use a 64-bit type for the count and for the totals.