Using hashing to solve 4-sum problem The famous 4-sum problem is to find 4 elements at unique indices in an array which sum to a given X. I was looking at one solution I found:
findFourElements(A[1], ..., A[n], X)

create hashtable mp
for each 1 ≤ i &lt; j ≤ n:
   mp[A[i] + A[j]] ← (i,j)     // (i,j) is an ordered pair
end for
for each 1 ≤ k &lt; l ≤ n:
   if mp contains A[k] + A[l]:
      (i,j) ← mp[X - (A[k] + A[l])]
      if i ∉ {k,l} and j ∉ {k,l}:
         return A(i),A(j),A(k),A(l)
      end if
   end if
end for

It is working fine on some test cases I tried. But I have a doubt: in the hashtable we are just storing one occurrence of each pair, but there can be a case in which a solution exists, but since we stored only one occurrence of each pair, we only have overlapping occurrences, and we may miss the non-overlapping ones. But still I am not able to produce any test case to fail it. Is this algorithm correct, or does it fail for some test case?
Suppose $A[i] + A[j] + A[k] + A[\ell] = X$. If there is a way to break this sum into two non-equal parts, then the problem you mention does not occur. Otherwise, we have
\begin{align}
A[i] + A[j] &amp;= A[k] + A[\ell] \\
A[i] + A[k] &amp;= A[j] + A[\ell] \\
A[i] + A[\ell] &amp;= A[j] + A[k]
\end{align}
In fact, all of these are equal to $X/2$, and this implies that $A[i] = A[j] = A[k] = A[\ell]$.
The hashtable entry for $X/2$ can only contain two of the indices $i,j,k,\ell$, say $i,j$ (it might contain fewer). The algorithm then finds the correct solution when it reaches $k,\ell$ in the second stage.