title: Codility MinAbsSum
body: <p>I tried this Codility test: MinAbsSum.
  <a href="https://codility.com/programmers/lessons/17-dynamic_programming/min_abs_sum/" rel="noreferrer">https://codility.com/programmers/lessons/17-dynamic_programming/min_abs_sum/</a></p>
  
  <p>I solved the problem by searching the whole tree of possibilities. The results were OK, however, my solution failed due to timeout for large input. In other words the time complexity was not as good as expected. My solution is O(nlogn), something normal with trees. But this coding test was in the section "Dynamic Programming", and there must be some way to improve it. I tried with summing the whole set first and then using this information, but always there is something missing in my solution. Does anybody have an idea on how to improve my solution using DP?</p>
  
  <pre><code>#include &lt;vector&gt;
  using namespace std;
  
  int sum(vector&lt;int&gt;&amp; A, size_t i, int s)
  {
     if (i == A.size())     
        return s;
  
     int tmpl = s + A[i];
     int tmpr = s - A[i];
     return min (abs(sum(A, i+1, tmpl)), abs(sum(A, i+1, tmpr)));
  }
  
  int solution(vector&lt;int&gt; &amp;A) {
     return sum(A, 0, 0);   
  }
  </code></pre>