Given a set s of integers, an integer total, and a non-negative integer budget, the subsetsumdecision problem is to report whether or not there is a subset of s, containing at most budget elements, that sums to total.

given a set s of integers, an integer total, and a non-negative integer budget, the subsetsumsearch problem is to find a subset of s, containing at most budget elements, that sums to total or to report that no such set exists.

a) suppose you have a polynomial time algorithm called ssd that solves the subsetsumdecision problem. describe, in clear and concise english, a polynomial time algorithm called sss that solves the subsetsumsearch problem. (hint: sss should call ssd multiple times.) you should not need more than five sentences or so.

b) suppose s is a set containing n integers, and that ssd(s, total, budget) is o(f( what of these is the tightest upper bound on the running time of sss(s, total, budget)?

a. o(n f(n))
b. o(f(n)^2)
c. o(f(n) log n)
d. o(f(n^2))