There is a pseudo-polynomial solution with dynamic programming which runs in $O(S n^2)$ with $S = \sum_{i=1}^n |a_i|$.
Namely for each possible sum $s$ (between $\sum_{a_i < 0} a_i$ and $\sum_{a_i > 0} a_i$) compute, if you can choose a subset of size $\lfloor n/2 \rfloor$ with sum $s$. Using this information you can directly find the optimal solution.
You can compute this information it in a similar way as you would for a 0/1 knapsack problem, just with one dimension more:
$$f(s, m, i) = f(s-a_i, m-1, i-1) ~\vee~ f(s, m, i-1)$$ if $i > 0$ and $m > 0$,
where $f(s, m, i)$ means "is it possible to choose a subset of size $m$ with sum $s$ using the first $i$ elements of the original array?".