Designing an algorithm to determine if a linear combination of k-1 sets is contained in the k-th set .

Question

I am trying to solve the following problem - given $k$ sets : $A_1,A_2,...,A_k$ containing $O(n)$ integers each I need to design an algorithm that will determine if there is such a group of elements $a_1\in A_1,$ $a_2\in A_2,\ldots,a_k\in A_k$ that will satisfy the equation: $a_1+a_2+\ldots+a_{k-1}=a_k.$ The required runtime is $O\left(n^{\frac{k}{2}}\log n\right)$ for even $k$'s and $O\left(n^{\frac{k+1}{2}}\right)$ for odd $k$'s. I'd be grateful for some ideas.

Answer 1

Here are some ideas that may help you. First, we can symmetrize the problem, by replacing each element of $A_k$ by its negative, then seek a solution to $$a_1+a_2+\cdots+a_{k-1}+a_k=0$$ We can also go the other way, negating appropriate elements to get $$a_1+a_2+\cdots+a_j=a_{j+1}+a_{j+2}+\cdots+a_k$$

So, a general approach is this: calculate $A_1+A_2+\cdots+A_j$, that is all the sums of one element from each set. Then, calculate $A_{j+1}+\cdots+A_k$. Then see if there is any intersection between these sumsets.

You don't have to put the first sets on the left, though, you can divide $\{A_1,\ldots, A_k\}$ between the left side and the right side as you like (probably to make them as equal in size as possible).