Multipart question part 13 anser part a The subsetsum proble

Multipart question part 1/3. anser part a)

The subset-sum problem. Let S = {s1....sn} 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 = {2,4,10,20,25}, t = 38, then
the answer is YES because 25 + 10 + 2 + 1 = 38. However, if S =
{1,2, 4, 10, 20, 25}, 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, s\'] = S\' if there exists a
subset of elements S\' in {s1...si} whose total value is s\', and
T[i, s\'] = * otherwise, * is a
flag indicating that no such S\' exists.
Show how T[0, k] can be easily computed for k = 0,....,s.

(b) If T[i, s\'] exists (T[i, s\'] != * ) and element si does not belong
to T[i, s\'], how can the value of T[i, s\'] be expressed using table
entries in previous rows? What about when T[i, s\'] exists and
element si belongs to T[i, s\']? Show how entry T[i, s\'] 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.

Solution

class subset_sum
{
   // Returns true if there is a subset of set[] with sum
       // equal to given sum
   static boolean subsetSum(int set[], int n, int sum)
   {
   // Base Cases
   if (sum == 0)
       return true;
   if (n == 0 && sum != 0)
       return false;
  
   // If last element is greater than sum, then ignore it
   if (set[n-1] > sum)
       return subsetSum(set, n-1, sum);
  
   /* else, check if sum can be obtained by any of the following
       (a) including the last element
       (b) excluding the last element */
   return subsetSum(set, n-1, sum) ||
                               subsetSum(set, n-1, sum-set[n-1]);
   }
   /* Driver program to test above function */
   public static void main (String args[])
   {
       int set[] = {1,2, 4, 10, 20, 25};
       int sum = 38;
       int n = set.length;
       if (subsetSum(set, n, sum) == true)
           System.out.println(\"Yes\");
       else
           System.out.println(\"No\");
   }
}