Does Any Quadruple Hit the Target
You are given four lists, each of n numbers, and a target. Print YES if it is possible to pick one number from each list so that the four add up to the target, and NO otherwise.
## What most people try first
Four nested loops, which is n^4 and hopeless at n = 2000.
Since only existence is asked and not a count, the honest first question is whether something cheaper than the counting version works. It does, and the difference is worth naming: existence needs a SET of first-half sums rather than a counting table, and it may stop the moment it finds a hit.
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 one half as a set, then scan the other
Put every a + b from the first two lists into a hash set. That is n^2 insertions. Then loop over every c + d from the last two lists and ask whether target minus c minus d is in the set. The first hit means YES, and finishing the loop without one means NO.
## Why it is correct
The four numbers add to the target exactly when (a + b) equals target minus (c + d). So a hit in the set means some first half completes some second half, which is a valid quadruple; and if no second half finds a partner then no quadruple exists, because every quadruple would have produced one.
## Why a set rather than a table here
For existence the multiplicity is irrelevant: one witness is as good as a thousand. So a set is the right structure, it is smaller, and it makes the early exit obvious. The counting version of this question genuinely needs the multiplicities, and using a set there is a wrong answer rather than an optimisation. Knowing which of the two you are being asked for is most of the skill.
## The boundary that breaks a careless implementation
Returning NO too early. The answer is NO only after the entire second-half loop has finished. A return of NO from inside the loop on the first MISS is a mistake that passes any test whose very first pair happens to hit, which is most small hand-made tests.
## Overflow
Values reach 10^9 in magnitude, so a half-sum reaches 2 * 10^9 and the full sum 4 * 10^9. Note carefully that 2 * 10^9 still fits in a signed 32-bit integer, since the limit is 2147483647, but 4 * 10^9 does not, and neither does a target of that size. So a 32-bit build can survive the half-sums and still be wrong about the target.
## Cost
n^2 insertions and up to n^2 lookups, four million each at n = 2000, against 1.6 * 10^13 for the nested loops.
## Worked example
``` A = 1 2 B = -2 -1 C = -1 2 D = 0 2 target 0
set of a + b: {-1, 0, 1}
c + d = -1 need 0 in the set -> YES, stop here ```
### Constraints - 1 <= n <= 2000 - each number is between -10^9 and 10^9 - the target is between -4 * 10^9 and 4 * 10^9 - A half-sum reaches 2 * 10^9 and the full sum 4 * 10^9, so sums and the target need a 64-bit type.