Question

5. Design a dynamic programming algorithm to solve the following problem.

Input: An array A[1, . . . , n] of positive integers, an integer K.

Decide: Are there integers in A such that their sum is K. (Return T RUE or F ALSE)

Example: The answer is TRUE for the array A = [1, 2, 3] and 5, since 2 + 3 = 5. The answer is FALSE for A = [2, 3, 4] and 8. Note that you have to solve this problem for any array of size n and any integer K. Do not just solve the problem for the sample inputs above.

Explain

• what subproblems one must solve for this problem,

• what the recursive solution is, and

• the algorithm in pseudocode format. Explain your work in detail. Answers without explanation will not receive full credit. (20 pt)

Answer 1

Here's a code in C:

// A Dynamic Programming solution
// for subset sum problem
#include <stdio.h>

// Returns true if there is a subset of set[]
// with sum equal to given k
bool isSubsetSum(int set[], int n, int k)
{
   // The value of subset[i][j] will be true if
   // there is a subset of set[0..j-1] with k
   // equal to i
   bool subset[n + 1][k + 1];

   // If sum is 0, then answer is true
   for (int i = 0; i <= n; i++)
       subset[i][0] = true;

   // If sum is not 0 and set is empty,
   // then answer is false
   for (int i = 1; i <= k; i++)
       subset[0][i] = false;

   // Fill the subset table in botton up manner
   for (int i = 1; i <= n; i++) {
       for (int j = 1; j <= k; j++) {
           if (j < set[i - 1])
               subset[i][j] = subset[i - 1][j];
           if (j >= set[i - 1])
               subset[i][j] = subset[i - 1][j]
                           || subset[i - 1][j - set[i - 1]];
       }
   }

   /* // uncomment this code to print table
   for (int i = 0; i <= n; i++)
   {
   for (int j = 0; j <= k; j++)
       printf ("%4d", subset[i][j]);
   printf("\n");
   }*/

   return subset[n][k];
}

// Driver program to test above function
int main()
{
   int set[] = { 3, 34, 4, 12, 5, 2 };
   int k = 9;
   int n = sizeof(set) / sizeof(set[0]);
   if (isSubsetSum(set, n, k) == true)
       printf("TRUE");
   else
       printf("FALSE");
   return 0;
}

i hope you understood the concept well. if you did, please click on the 'like' button.

Also if you have any doubt regarding any concept taught above, do mention in the comments. i will try to answer it as soon as possible.