3-PARTITION problem

Question

here is another dynamic programming question (Vazirani ch6)

Consider the following 3-PARTITION problem. Given integers a1...an, we want to determine whether it is possible to partition of {1...n} into three disjoint subsets I, J, K such that

sum(I) = sum(J) = sum(K) = 1/3*sum(ALL)

For example, for input (1; 2; 3; 4; 4; 5; 8) the answer is yes, because there is the partition (1; 8), (4; 5), (2; 3; 4). On the other hand, for input (2; 2; 3; 5) the answer is no. Devise and analyze a dynamic programming algorithm for 3-PARTITION that runs in time poly- nomial in n and (Sum a_i)

How can I solve this problem? I know 2-partition but still can't solve it

Answer 1

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 :)