I have a sequence ( n, n-1, n-2,...,1). I need to find numbers in this sequence in this order that somewhat approximately divide it into M parts- within each M subgroup the sum is somewhat the same. Is there a general way to do it? 


For example, 5,4,3,2,1 - for M=3, it could be 5; 4; 3,2,1 where the sums are somewhat close (5,4,6). 
Or 8,7,6,5,4,3,2,1 - For M=3 maybe 8;7+6=13;(rest)15. 
8;13;15 is good enough split(15;11;10 is also okay and arguably better than 8,13,15). I don't need it to be exactly equal but for a value of n, M is there a general way to approximately split it? In my case, n is very large( 1000s) and M is probably no greater than 8 at most. 



Subdividing a sequence such that sum is somewhat equally distributed
You can solve the problem exactly as a shortest path problem in a layered network. The nodes are $(i,k)$, where $i\in\{n,\dots,1\}$ and $k\in\{1,\dots,M\}$. The (directed) arcs are from $(i,k)$ to $(j,k+1)$ with $j<i$. The idea is that traversing arc $(i,k)\to (j,k+1)$ means that $\{i,i-1,\dots,j+1\}$ comprise a part. The cost of this arc is the (absolute, or squared, or any type of) deviation from the target $n(n+1)/(2M)$. Because the network is acyclic, you can solve the problem in $O(M n^2)$ time, that is, linear in the number of arcs.


Alternatively, a greedy heuristic could be to start a new part $p+1$ whenever including the next number would make the cumulative sum exceed $pn(n+1)/(2M)$. For $n=5$ and $M=3$, this yields $5;4;3+2+1$. For $n=8$ and $M=3$, this yields $8;7+6;5+4+3+2+1$.


