= Three-way equal-sum partition dynamic programming
{title2=$D_i(x,y)$}
For <positive integer> weights of total $S=3h$, store reachable pairs $(x,y)$ of sums assigned to the first two groups after each input <list prefix>. The third sum is determined by the processed total minus $x+y$. Assign each new occurrence to one of the three groups using a fresh layer; accept exactly final state $(h,h)$. The transitions are sound by construction and complete by deleting the last occurrence from a valid assignment. The state range is $0\leq x,y\leq h$, giving $O(n(h+1)^2)$ time and $O((h+1)^2)$ rolling space.
Back to article page
