Here is the problem:

I have 3 subsets ( called $S_1$, $S_2$ and $S_3$) that each have $N$ elements (arbitrary elements).

So I have one element $X$. I want to know if I can get $X$ making the sum of one element of $S_1$, one of $S_2$ and one of $S_3$.

Say for example $N = 4$ and $S_1 = \{ 1, 3,-1, 5\}$, $S_2 = \{ 4, 0, 2, 1 \}$, $S_3 = \{ 5, 1, 0, 6\}$.

Then

$X = 11$ returnss YES because picking $3$ in $S_1$, $2$ in $S_2$ and $6$ in $S_3$, we can make the sum $3 + 2 + 6 = 11$,

$X = 10$ returns YES ($5 + 0 + 5$)

$X = 1$ returns YES ($ 1 + 0 + 0 $) or ($ -1 + 2 + 0$ )

$X = 20$ returns false

If I sum all the possibilities, clearly we get an $O(n^3)$ algorithm.

As mentioned in the title, the question is if there is an $O(n^2)$ algorithm for this problem.

sortof right... – Noam D. Elkies Jul 3 '13 at 19:12