# 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.

• Can you explain what the tug of war problem is? Commented Jul 27, 2018 at 10:42
• geeksforgeeks.org/tug-of-war for problem explanation. Commented Jul 27, 2018 at 14:09
• Your problem is NP-hard, by reduction from PARTITION. Commented Jul 27, 2018 at 14:13
• Please make your question self-contained, so we can understand the problem without visiting the link (and so if the link stops working the question still makes sense). Also, what have you tried? We have a guide on dynamic programming: cs.stackexchange.com/tags/dynamic-programming/info. It would be more helpful for you to try the systematic approach listed there, then show what progress you've made so far in the question, before asking.
– D.W.
Commented Jul 27, 2018 at 19:23

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.
$$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?".