Let $A_1,A_2 \dots A_k $ be sets of integers such that $\left|A_{1}\right|+\left|A_{2}\right|+\dots\left|A_{k}\right|=\mathcal{O}\left(n\right) $
Find an algorithm that determines if there are $a_1+a_2+a_3+\dots a_{k-1}=a_k $ such that $a_i\in A_i $ with runtimes of $O\left(n^{\frac{k}{2}}\log\left(n\right)\right)$ for even k and $O\left(n^{\frac{k+1}{2}}\right) $ for odd k. How to find an algorithm for odd k's and even k's where k is non-constant?
So I started looking at the case of $k=2 $ and with sorting both arrays, and binary searching $a_1 $ for all $a_1\in A_1$ we can determine a solution with $$ T=\mathcal{O}\left(\overbrace{n\log\left(n\right)}^{Sort}\right)+\mathcal{O}\left(\overbrace{n}^{loop}\cdot\overbrace{\log\left(n\right)}^{B.S}\right) $$
For Even K I determined the equation can be $a_{1}+a_{2}+a_{3}+\dots a_{k-1}-a_{k}=0 $ I split the arrays into 2 sets such that $$ \overbrace{\left\{ A_{1},A_{2},A_{3}\dots A_{\frac{k}{2}}\right\} }^{Q},\overbrace{\left\{ A_{\frac{k}{2}+1},A_{\frac{k}{2}+2}\dots-A_{k}\right\} }^{P} $$
at most each $A_i $ has $n $ elements so the number of sums possible is $n^\frac{k}{2}$ for $P$ and the same is true for $Q$. Afterwards I can use sort and binary search, just as in $k=2$, but the runtime for sorting is $\mathcal{O}\left(n^{\frac{k}{2}}\log\left(n^{\frac{k}{2}}\right)\right)=\mathcal{O}\left(kn^{\frac{k}{2}}\log\left(n\right)\right) $ and for non constant-k it does not work.
For odd k I don't have an idea, since looking at the runtime no sorting is needed, it seems like a completely different problem.
