Question

Write a program that will read a list of numbers and a desired sum, then determine the subset of ...

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.

0 0
Add a comment Improve this question Transcribed image text
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-

© Write A Program That Will Read + Online C++ Compiler-online ecX + a https://www.onlinegdb.com/online c++_compiler Apps SG I

Add a comment
Know the answer?
Add Answer to:
Write a program that will read a list of numbers and a desired sum, then determine the subset of ...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • Write a program that will read a list of numbers and a desired sum, then determine...

    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...

  • Write a program that will read a list of numbers and a desired sum, then determine...

    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) Using JAVA 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...

  • Write a C PROGRAM that will read in 10 floating-point numbers from the keyboard and load...

    Write a C PROGRAM that will read in 10 floating-point numbers from the keyboard and load them into an array. Add up all the values and store the answer in a variable. Find the largest and smallest number in the array. Put each into its own variable. Print to the screen the sum, largest value, and smallest value. Copy the array to a second array in reverse order. Print out the second array. Read in 20 integer numbers, all in...

  • please use C++ write a program to read a textfile containing a list of books. each...

    please use C++ write a program to read a textfile containing a list of books. each line in the file has tile, ... Question: Write a program to read a textfile containing a list of books. each line in the file has tile, ..... write a program to read a textfile containing a list of books. each line in the file has tile, ... Question: Write a program to read a textfile containing a list of books. Each line in...

  • In C++ Write a menu driven C++ program to read a file containing information for a list of Students, process the data, t...

    In C++ Write a menu driven C++ program to read a file containing information for a list of Students, process the data, then present a menu to the user, and at the end print a final report shown below. You may(should) use the structures you developed for the previous assignment to make it easier to complete this assignment, but it is not required. Required Menu Operations are: Read Students’ data from a file to update the list (refer to sample...

  • in java PART ONE ================================================== Write a program that will read employee earnings data from an...

    in java PART ONE ================================================== Write a program that will read employee earnings data from an external file and then sort and display that data. Copy and paste the input file data below into an external file, which your program will then read. You will want to use parallel arrays for this program. Modify the select sort algorithm to receive both arrays as parameters as well as the size of the arrays. Use the algorithm to sort your earnings array....

  • Write a program that can read XML files for customer accounts receivable, such as <ar>        <customerAccounts>...

    Write a program that can read XML files for customer accounts receivable, such as <ar>        <customerAccounts>               <customerAccount>                       <name>Apple County Grocery</name>                       <accountNumber>1001</accountNumber>                       <balance>1565.99</balance>               </customerAccount>               <customerAccount>                       <name>Uptown Grill</name>                       <accountNumber>1002</accountNumber>                       <balance>875.20</balance>               </customerAccount>        </customerAccounts>        <transactions>               <payment>                       <accountNumber>1002</accountNumber>                       <amount>875.20</amount>               </payment>               <purchase>                       <accountNumber>1002</accountNumber>                       <amount>400.00</amount>               </purchase>               <purchase>                       <accountNumber>1001</accountNumber>                       <amount>99.99</amount>               </purchase>               <payment>                       <accountNumber>1001</accountNumber>                       <amount>1465.98</amount>               </payment>        </transactions>     </ar> Your program should construct an CustomerAccountsParser object, parse the XML data & create new CustomerAccount objects in the CustomerAccountsParser for each of the products the XML data, execute all of...

  • Infix Expression Evaluator For this project, write a C program that will evaluate an infix expression. The algorithm REQ...

    Infix Expression Evaluator For this project, write a C program that will evaluate an infix expression. The algorithm REQUIRED for this program will use two stacks, an operator stack and a value stack. Both stacks MUST be implemented using a linked list. For this program, you are to write functions for the linked list stacks with the following names: int isEmpty (stack); void push (stack, data); data top (stack); void pop (stack); // return TRUE if the stack has no...

  • Infix Expression Evaluator For this project, write a C program that will evaluate an infix expression. The algorithm REQ...

    Infix Expression Evaluator For this project, write a C program that will evaluate an infix expression. The algorithm REQUIRED for this program will use two stacks, an operator stack and a value stack. Both stacks MUST be implemented using a linked list. For this program, you are to write functions for the linked list stacks with the following names: int isEmpty (stack); void push (stack, data); data top (stack); void pop (stack); // return TRUE if the stack has no...

  • This is in C. For this assignment we will write a simple database server. We will...

    This is in C. For this assignment we will write a simple database server. We will be creating a simple database of student records, so let’s describe these first. The format of a student record is as follows: typedef struct student {     char lname[ 10 ], initial, fname[ 10 ];     unsigned long SID;     float GPA; } SREC; Part One – the Server We will create a database server. The job of the server is to accept a...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT