9. (7 points) Given a set S of n numbers, the k-partition problem is to determinewhether or not S can be partitioned into k subsets of the same sum. Forexample, let S ={1,2,9,12,18}. Then for the two-partition problem, we indeedcan partition S into two subsets S1 = {1,2,18} and S2 = {9,12} such that thesum of all elements in S1 equals to the sum of all elements in S2. In fact, it canbe proved that the two-partition problem is NP-complete. In the situation wherethe two-partition problem is already NP-complete, please prove that thethree-partition problem is also NP-complete.