Question

Create a simple main() that solves the subset sum problem for any vector ofints. Here is an example of the set-up and output. You would fill in the actual code that makes it happen. I want the code to produce a result like the output please do not copy random stuff from google.Code:int main(){ int TARGET = 180; vector dataSet; vector choices; vector::iterator iter, iterBest; int k, j, numSets, max, masterSum; bool foundPerfect; dataSet.push_back(20); dataSet.push_back(12); dataSet.push_back(22); dataSet.push_back(15); dataSet.push_back(25); dataSet.push_back(19); dataSet.push_back(29); dataSet.push_back(18); dataSet.push_back(11); dataSet.push_back(13); dataSet.push_back(17); choices.clear(); cout << "Target time: " << TARGET << endl; // code provided by student iterBest->showSublist(); return 0; }

Answer 1

The main function is given below. Appropriate comments are made where necessary. In addition to this, I added a full code for the problem to help you understand it fully

Step-by-step explanation:

// Sublist.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include <iostream>

#include <vector>

using namespace std;

int sumInStack = 0;

int TARGET_SUM = 180;

vector<int> choices;

void subList(vector<int> data, int fromIndex, int endIndex);

void print();

int main()

{

vector<int> dataSet;

int k, j, fromIndex,endIndex;

bool foundPerfect;

dataSet.push_back(20); dataSet.push_back(12); dataSet.push_back(22);

dataSet.push_back(15); dataSet.push_back(25);

dataSet.push_back(19); dataSet.push_back(29);

dataSet.push_back(18);

dataSet.push_back(11); dataSet.push_back(13); dataSet.push_back(17);

choices.clear();

fromIndex=0;

endIndex=dataSet.size();

cout << "Target time: " << TARGET_SUM << endl;

subList(dataSet, fromIndex, endIndex);

// code provided by student

system("pause");

return 0;

}

void subList(vector<int> data, int fromIndex, int endIndex) {

/*

* Check if sum of elements stored in Stack is equal to the expected

* target sum.

*

* If so, call print method to print the candidate satisfied result.

*/

if (sumInStack == TARGET_SUM)

{

print();

}

for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++)

{

if (sumInStack + data[currentIndex] <= TARGET_SUM)

{

choices.push_back(data[currentIndex]);

sumInStack += data[currentIndex];

/*

* Make the currentIndex +1, and then use recursion to proceed

* further.

*/

subList(data, currentIndex + 1, endIndex);

sumInStack -= choices.back();

choices.pop_back();

}

}

}

void print()

{

cout<<TARGET_SUM<<" = ";

for(int i=0;i<choices.size();i++)

{

cout<<choices.at(i)<<"+";

}

}