= Four-sum problem
= 4-sum
{synonym}
The <four-sum problem> asks whether four selected numbers sum to a target $t$, with the selection rules part of the input specification. In the four-list version, choose one value from each of $A,B,C,D$. Store sums $a+b$ and look for $t-(c+d)$, a <meet-in-the-middle algorithm>. For lists of length $n$, hashing gives expected $O(n^2)$ time and $O(n^2)$ storage; sorting pair sums gives deterministic comparison-based alternatives. In a single-list version requiring four distinct positions, stored pairs must also satisfy the index-disjointness condition. Equal values and equal positions are different restrictions.
Back to article page
