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

Question

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.

Answer 1

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.