3-PARTITION problem
I think by reduction it goes like this:
Reducing 2-partition to 3-partition:
Let S be the original set, and A be its total sum, then let S'=union({A/2},S). Hence, perform a 3-partition on the set S' yields three sets X, Y, Z. Among X, Y, Z, one of them must be {A/2}, say it's set Z, then X and Y is a 2-partition. The witnesses of 3-partition on S' is the witnesses of 2-partition on S, thus 2-partition reduces to 3-partition.
It's easy to generalize 2-sets solution for 3-sets case.
In original version, you create array of boolean sums
where sums[i]
tells whether sum i
can be reached with numbers from the set, or not. Then, once array is created, you just see if sums[TOTAL/2]
is true
or not.
Since you said you know old version already, I'll describe only difference between them.
In 3-partition case, you keep array of boolean sums
, where sums[i][j]
tells whether first set can have sum i
and second - sum j
. Then, once array is created, you just see if sums[TOTAL/3][TOTAL/3]
is true
or not.
If original complexity is O(TOTAL*n)
, here it's O(TOTAL^2*n)
.
It may not be polynomial in the strictest sense of the word, but then original version isn't strictly polynomial too :)