Design an exhaustive search or optimization algorithm that solves the problem; describe your algorithm with clear pseudocode, and prove the time efficiency class of your algorithm. When writing your pseudocode, you can assume that your audience is familiar with the candidate generation algorithms in this chapter, so you can make statements like for each subset X of S without explaining the details of how to generate subsets.

1) subset sum problem

def sumSubset(X, k):

2)

input: a list X of n distinct integers, and a target integer k output: a subset SSX such that k = rest, or None if no such S exists set partition problem input: list of X of n distinct positive integers output: a pair of lists (L, R) such that L and R form a set partition X = LUR and Ziell = {reRT, or None if no such partition exists