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

Answer:

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

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)<<"+";

    }

}