The subset-sum problem. Let S = fs1; : : : ; sng be a set of n positive integers and let t be a positive integer called the target. The subset-sum problem is to decide if S contains a subset of elements that sum to t. For example, if S = f1; 2; 4; 10; 20; 25g, t = 38, then the answer is YES because 25 + 10 + 2 + 1 = 38. However, if S = f1; 2; 4; 10; 20; 25g, t = 18, then the answer is NO. Let s = s1+: : :+sn.

(a) Let T[0::n; 0::s] be a table such that T[i; s0] = S0 if there exists a subset of elements S0 in fs1; : : : ; sig whose total value is s0, and T[i; s0] = y otherwise; y is a ag indicating that no such S0 exists. Show how T[0; k] can be easily computed for k = 0; : : : ; s.

(b) If T[i; s0] exists (T[i; s0] 6= y) and element si does not belong to T[i; s0], how can the value of T[i; s0] be expressed using table entries in previous rows? What about when T[i; s0] exists and element si belongs to T[i; s0]? Show how entry T[i; s0] can be computed from table entries in previous rows.

(c) Design an O(n s) time algorithm that decides if S contains a subset of elements A that sum to t. 2