Can Tug of war problem be solved by DP or greedy approach? For problem explanation: https://www.geeksforgeeks.org/tug-of-war/

I know the exponential solution to the problem, but can it be improved by greedy or DP approach. If yes then please explain the ideology of the solution. Also please mention if there are exceptions to this greedy or DP solution where it may not apply.
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 &lt; 0} a_i$ and $\sum_{a_i &gt; 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 &gt; 0$ and $m &gt; 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?".