# algorithm that determines if there are $a_1+a_2+\dots a_{k-1} =a_k$

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.