title: 3-PARTITION problem
body: <p>here is another dynamic programming question (<a href="http://www.cs.berkeley.edu/%7Evazirani/algorithms/chap6.pdf" rel="noreferrer">Vazirani ch6</a>)</p>
  <blockquote>
  <p>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</p>
  <p>sum(I) = sum(J) = sum(K) = 1/3*sum(ALL)
  <br></p>
  <p>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)</p>
  </blockquote>
  <p>How can I solve this problem? I know 2-partition but still can't solve it</p>