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 


1. $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$,
2. $X = 10$ returns YES ($5 + 0 + 5$)
3. $X = 1$ returns YES ($ 1 + 0 + 0 $) or ($ -1 + 2 + 0$ )
4. $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. 



Algorithm to find if an element X can be represented with the sum of one number of each subset in $O(n^2)$?
First sort $S\_2$ and $S\_3$.


Divide into $n$ subproblems: for each $a\in S\_1$, look for $b\in S\_2,c\in S\_3$ such that $b+c=X-a$. Let's do one such subproblem in $O(n)$ time.


Let $b\_j$ be the $j$-th element of $S\_2$ and $c\_k$ be the $k$-th element of $S\_3$. The idea is that for $j=1,2,\ldots,n$ you find the smallest $k$ such that $b\_j+c\_k\ge X-a$. For each $j$ find $k$ by starting at the previous value, not by searching from the end. As $j$ increases, $k$ stays the same or decreases, so you only need to move $k$ at most $n$ times in total.


