Quadruples Hitting a Target
You are given four lists, each of n numbers, and a target. Count the ways to pick exactly one number from each list so that the four picked numbers add up to the target. Print the count.
Two ways are different if they pick a different POSITION in any list, even when the values are equal. So picking the first 0 out of a list differs from picking the second 0.
## What most people try first
Four nested loops, which is n^4. At n = 1000 that is 10^12 and hopeless.
The next idea is usually to sort everything and two-point the ends, which works beautifully for two lists and does not generalise to four, because fixing one number still leaves a three-way problem.
A word on what is being halved, because this is the step students most often get backwards after seeing the subset versions of this technique.
In the subset problems the INPUT LIST is cut in two. Here the input list is not cut at all. What is cut in two is the ANSWER: a quadruple is split into its first two coordinates and its last two. Each half of the quadruple is tabulated in O(n^2), and the two tables are joined. So "meet in the middle" refers to meeting in the middle of the tuple, not the middle of the array.
The reason it pays off is the same in both cases. The work is quadratic in the number of coordinates you enumerate at once, so enumerating two at a time instead of four turns n^4 into n^2.
## Tabulate the first half, then look up the second
Build a table of every sum a + b over the first two lists. That is n^2 sums, a million at n = 1000, and the table maps each sum to HOW MANY (a, b) position pairs produce it.
Then loop over every c + d from the last two lists, also n^2 of them, and for each one add the table's count for target minus c minus d.
## Why it is correct
Every quadruple (a, b, c, d) summing to the target has exactly one first half and exactly one second half, and any first half whose sum is s pairs with any second half whose sum is target minus s. So the quadruples are in one-to-one correspondence with the matching pairs of halves, and summing the table's counts over all second halves counts each quadruple exactly once.
## The boundary that breaks a careless implementation
Storing the first-half sums in a SET rather than a counting table. A set loses the multiplicity, and the answer collapses: four lists of two zeros each with target 0 should give 16, and a set-based solution gives 1. Position pairs are what is being counted, not distinct sums.
The second is the type of the answer. With n = 250 and every number 0 and the target 0, every one of the 250^4 quadruples qualifies, and 250^4 is 3906250000. That is past the 32-bit signed limit of 2147483647.
## Overflow
Values reach 10^9 in magnitude, so a + b reaches 2 * 10^9 and the full four-way sum reaches 4 * 10^9. Both the sums and the count need 64 bits. The target itself can reach 4 * 10^9 in magnitude.
## Cost
n^2 to build the table, n^2 lookups. A couple of million steps at n = 1000, against 10^12.
## Worked example
``` A = 1 2 B = -2 -1 C = -1 2 D = 0 2 target 0
sums of A and B: 1 + -2 = -1, 1 + -1 = 0, 2 + -2 = 0, 2 + -1 = 1 table: {-1: 1, 0: 2, 1: 1}
sums of C and D: -1 + 0 = -1, -1 + 2 = 1, 2 + 0 = 2, 2 + 2 = 4 c + d = -1 need 1 table has 1 adds 1 c + d = 1 need -1 table has 1 adds 1 c + d = 2 need -2 absent adds 0 c + d = 4 need -4 absent adds 0
answer 2 ```
### Constraints - 1 <= n <= 1000 - each number is between -10^9 and 10^9 - the target is between -4 * 10^9 and 4 * 10^9 - The count reaches n^4, which is 10^12 at n = 1000, so the count needs a 64-bit type as well as the sums.