Question

Write a program that will read a list of numbers and a desired sum, then determine the subset of numbers in the list that yield that sum if such a subset exists.

Answer from Data Structures (2nd Edition) Chapter 5.6, Problem 6PP: Does not fully answer the question. Specifically, ". . . then determine the subset of numbers in the list that yield that sum if such a subset exists" is not answered in provided solution. It should show the actual subsets that can be made to add up to the sum.

Answer 1

Code -

#include <bits/stdc++.h>
using namespace std;

bool** dp;

void displaySubset(const vector<int>& v)
{
   for (int i = 0; i < v.size(); ++i)
       printf("%d ", v[i]);
   printf("\n");
}

//it is a recursive function to print the subset
void printSubset(int list[], int i, int sum, vector<int>& p)
{
//if we reach end and sum is nonzero and we will print only of the list[0] is equal to sum
   if (i == 0 && sum != 0 && dp[0][sum])
   {
       p.push_back(list[i]);
       displaySubset(p);
       return;
   }

   //condition to check sum is zero
   if (i == 0 && sum == 0)
   {
       displaySubset(p);
       return;
   }

   //sum can be achieved by ignoring the current element
   if (dp[i-1][sum])
   {
       //create a new vector
       vector<int> b = p;
       printSubset(list, i-1, sum, b);
   }

   //sum can be achieved by considrring current element
   if (sum >= list[i] && dp[i-1][sum-list[i]])
   {
       p.push_back(list[i]);
       printSubset(list, i-1, sum-list[i], p);
   }
}
//function print all the subset
void printAllSubset(int list[], int n, int sum)
{
   if (n == 0 || sum < 0)
   return;

   dp = new bool*[n];
   for (int i=0; i<n; ++i)
   {
       dp[i] = new bool[sum + 1];
       dp[i][0] = true;
   }

   // Sum list[0] can be achieved with single element
   if (list[0] <= sum)
   dp[0][list[0]] = true;

   //fill the rest of entries in dp
   for (int i = 1; i < n; ++i)
       for (int j = 0; j < sum + 1; ++j)
           dp[i][j] = (list[i] <= j) ? dp[i-1][j] ||
                                   dp[i-1][j-list[i]]
                                   : dp[i - 1][j];
   if (dp[n-1][sum] == false)
   {
       printf("There are no subsets with sum %d\n", sum);
       return;
   }

   vector<int> p;
   printSubset(list, n-1, sum, p);
}

// Driver code
int main()
{
   int list[] = {1, 2, 3, 4, 5,6,7,8,9};
   int n = sizeof(list)/sizeof(list[0]);
   int sum = 15;
cout<<"For sum " <<sum<<" subsets are "<<endl;
   printAllSubset(list, n, sum);
   return 0;
}

Screenshots-