# Algorithm to find if an element X can be represented with the sum of one number of each subset in $O(n^2)$?

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.

-
I tried sum all numbers in S1 and S2, and search the number that i want ( S1+S2 - X ) in S3, but still a n³ – Shermano Jul 3 '13 at 19:08
sorry my poor english – Shermano Jul 3 '13 at 19:09
That's, um, sort of right... – Noam D. Elkies Jul 3 '13 at 19:12
sorry ?? i don't get it – Shermano Jul 3 '13 at 19:18
It's easy to do in $O(n^2)$, but is this a homework question? – Brendan McKay Jul 3 '13 at 20:38

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.