Question

Write a solution to the subset sum problem using Drracket. Write a procedure (subset-sum n nums) where n is an integer and nums is a list of numbers that returns a subset of the numbers in the list nums whose values sum to n. If no subset of nums does this, the function should return #f.

Ex: (subset-sum 12 '(2 10 5 7 3 8 6)) returns '(2 10) or any other subset of '(2 10 5 7 3 8 6) that sums to 12; (subset-sum 17 '(2 10 6)) returns #f.

Answer 1

1 this is done in c++

#include <stdio.h>

// Returns true if there is a subset of set[]

// with sun equal to given sum

bool isSubsetSum(int set[], int n, int sum)

{

    // The value of subset[i][j] will be true if

    // there is a subset of set[0..j-1] with sum

    // equal to i

    bool subset[n + 1][sum + 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 <= sum; 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 <= sum; 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 <= sum; j++)

          printf ("%4d", subset[i][j]);

       printf("\n");

     }*/

    return subset[n][sum];

}

// Driver program to test above function

int main()

{

    int set[] = { 3, 34, 4, 12, 5, 2 };

    int sum = 9;

    int n = sizeof(set) / sizeof(set[0]);

    if (isSubsetSum(set, n, sum) == true)

        printf("Found a subset with given sum");

    else

        printf("No subset with given sum");

    return 0;

}