No, you shouldn't consider all combinations. This is DP, it's all about avoiding cases where you can't get a result. This problem is solved this way: Let: x=sum(k=1, i-1)a[k]; y=sum(k=i, j)a[k]; z=sum(k=j+1, n)a[k]; and s=sum(k=1, n)a[k], the sum of all numbers in the array We observe that x+y+z=s, and how x=y=z (that's what the problem states) => 3*x=3*y=3*c=z, thus x=y=z=s/3. You can figure it out from here, but here is the rest of the solution (dont't read unless you gave up on the problem): Let v be an array such as v[i]=sum(k=1, i)a[k]. If vn is not divisible by 3, that means we can't divide s into three equal parts. Now, we will work with the sums in the array v. So, how x=y=z=s/3, we need to find all sums equal with s/3. The number of ways we can achieve that sum is the number of x's we can obtain. Afterwards, when we can no longer obtain s/3, we try to obtain 2*s/3 (from array v), that is x+y. When we find one, we add the number of ways of getting x to the solution. The code looks something like this: http://codeforces.net/contest/466/submission/11713930

If you consider all possible combinations, then it's not DP, but brute froce. Anyway, this problem is something else.

Let S be the sum of all elements. First of all, if that sum is not a multiple of 3, then the answer is 0. OK, now calculate L_i, which means how many positions p are there with p ≤ i such that the sum of all elements from 1 to p is equal to . Then iterate from the right (from N down to 1) and keep track of the sum of all elements so far. If at position i, that sum is , add L_i - 2 to the answer (you must have at least one element in the middle section).