Can Tug of war problem be solved by DP or greedy approach?
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?".