Prove that each of following problems is in P by sketching a polynomial time algorithm that solves it. Briefly justify that your algorithm runs in polynomial.

(2) LARGE-SUBSET = {S,k,t | S = {x1,...,xn} is a set of positive k

numbers such there exists a set {y1,...,yk} S where yi t} i=1

Hint: Note that you have to use exactly k elements of S for this variant of SUBSET-SUM where k is specified by the user.