3. Given a list of n > 0 strictly positive integers, X-(11, 12,.,Tn } whose sum is s = -1 Tg we want to determine if it is possible to partition X into three mutually disjoint subsets, say A1, A2, and Ag, such that iEAi 1jEA2 kEA3 Moreover, if such a partitioning is possible, we wish to find suitable subsets. For example, given X 1,2,3,4,4,5,8 we find that the answer is yes it is possible Specifically, a suitable partition of X is A1 (1,8), A2-4,5), and As-(2,3,4) Note that these sublists each sum to 9, which is one third of the sum over all X Alternatively, if we were given X-(2, 2, 3,5), then S = .ri-12, but there is no way to partition this into three sublists which all sum to 12/3-4. In this case the answer is no, it is not possible to find such a solution a. Clearly describe a dynamic programming algorithm for returning "yes" or "no", corre- sponding to whether or not such a partitioning is possible. Your algorithm must run in time O(n x S2). Explain why you believe the algorithm and your runtime estimate are correct, but you do not need to provide detailed proofs. Hint: T(m, u,v) f there are disjoint subsets of X.m that sum to u and v 0 otherwise b. Assuming your algorithm runs in time (n x S2), is this a polynomial time algorithm? Briefly explain. c. In situations where part (a) returns "yes", that is, when a solution exists, clearly explain how to find suitable partition sets, namely A1, A2, and Ag. (You should build on your solution in part (a).) 3. Given a list of n > 0 strictly positive integers, X-(11, 12,.,Tn } whose sum is s = -1 Tg we want to determine if it is possible to partition X into three mutually disjoint subsets, say A1, A2, and Ag, such that iEAi 1jEA2 kEA3 Moreover, if such a partitioning is possible, we wish to find suitable subsets. For example, given X 1,2,3,4,4,5,8 we find that the answer is yes it is possible Specifically, a suitable partition of X is A1 (1,8), A2-4,5), and As-(2,3,4) Note that these sublists each sum to 9, which is one third of the sum over all X Alternatively, if we were given X-(2, 2, 3,5), then S = .ri-12, but there is no way to partition this into three sublists which all sum to 12/3-4. In this case the answer is no, it is not possible to find such a solution a. Clearly describe a dynamic programming algorithm for returning "yes" or "no", corre- sponding to whether or not such a partitioning is possible. Your algorithm must run in time O(n x S2). Explain why you believe the algorithm and your runtime estimate are correct, but you do not need to provide detailed proofs. Hint: T(m, u,v) f there are disjoint subsets of X.m that sum to u and v 0 otherwise b. Assuming your algorithm runs in time (n x S2), is this a polynomial time algorithm? Briefly explain. c. In situations where part (a) returns "yes", that is, when a solution exists, clearly explain how to find suitable partition sets, namely A1, A2, and Ag. (You should build on your solution in part (a).)