Let again be the total. Reject unless is divisible by three, and put . Define to mean that the first occurrences can be assigned to three groups so that the first two groups have sums and . Their third sum is already determined by the processed list prefix sum minus , so it need not be stored as another coordinate.
Initialize true and all other states false. For each reachable state, assign the next occurrence to exactly one group: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 , the third sum is , giving precisely the required disjoint partition.
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]There are states per layer and a constant number of transitions per state. Thus the time is , and rolling layers use space for nonempty inputs. The source mentions an additional integer in this part, but it does not occur in the stated equal-partition condition; the required target is determined by . Empty groups are allowed by the stated subset formulation.
Articles by others on the same topic
There are currently no matching articles.