申論題

9. (7 points) Given a set S of n numbers, the k-partition problem is to determine whether or not S can be partitioned into k subsets of the same sum. For example, let S ={1,2,9,12,18}. Then for the two-partition problem, we indeed can partition S into two subsets S₁ = {1,2,18} and S₂ = {9,12} such that the sum of all elements in S₁ equals to the sum of all elements in S₂. In fact, it can be proved that the two-partition problem is NP-complete. In the situation where the two-partition problem is already NP-complete, please prove that the three-partition problem is also NP-complete.