= Solution
Let $S$ again be the total. Reject unless $S$ is divisible by three, and put $h=S/3$. Define $D_i(x,y)$ to mean that the first $i$ occurrences can be assigned to three groups so that the first two groups have sums $x$ and $y$. Their third sum is already determined by the processed <list prefix> sum minus $x+y$, so it need not be stored as another coordinate.
Initialize $D_0(0,0)$ true and all other states false. For each reachable state, assign the next occurrence to exactly one group:
``
threeEqualParts(A):
S = sum of A
if S mod 3 != 0: return false
h = S/3
D[0..h,0..h] = false
D[0,0] = true
for each indexed entry a in A:
Next[0..h,0..h] = false
for x from 0 to h:
for y from 0 to h:
if D[x,y]:
Next[x,y] = true
if x+a <= h: Next[x+a,y] = true
if y+a <= h: Next[x,y+a] = true
D = Next
return D[h,h]
``
The three transitions put the occurrence in the third, first or second group, respectively. Using a fresh layer prevents reusing it. Conversely, deleting the last occurrence from any valid <list prefix> assignment leaves exactly one predecessor state, so <induction> proves completeness as well as soundness. At the final state $(h,h)$, the third sum is $S-2h=h$, giving precisely the required disjoint partition.
There are $(h+1)^2$ states per layer and a constant number of transitions per state. Thus the time is \b[$O(n(h+1)^2)\subseteq O(n^3k^2)$], and rolling layers use \b[$O((h+1)^2)\subseteq O(n^2k^2)$] space for nonempty inputs. The source mentions an additional <integer> $s$ in this part, but it does not occur in the stated equal-partition condition; the required target is determined by $S$. Empty groups are allowed by the stated <subset> formulation.
Back to article page
