Sum Of Subsets Program

Question

I am new to C++ and am writing a sum of subsets program that takes in a user defined set of numbers, the first number of which is considered to be the total. I have tried using DDD to debug this program, however I continue to get an out-of-bounds error. I cannot seem to find out why this is happening. Any clues? Thanks. Here is the error:

terminate called after throwing an instance of 'std::out_of_range'
what(): vector::_M_range_check

Code:

#include <iostream>
#include <vector>
#include <cassert>
#include <iomanip>
#include <climits>
#include <math.h>
#include <algorithm>

typedef unsigned int uint;
using namespace std;

//////// Function declerations //////////
void sum_of_subsets( uint index, 
                     uint weight, 
                     uint total, 
                     vector<bool> &include, 
                     vector<uint> &w,
                     uint W );

bool promising ( uint index, 
                 uint weight, 
                 uint W, 
                 vector<uint> w,
                 uint total );

.

/////////////// Main //////////////////
int main()
{
    //string sortingCode = "-as";
    vector<uint> w;             // vector of weights
    vector<bool> include;       
        uint W;                     // the total
    uint index = 0;
    uint weight = 0;            // the current weight of subsets
    uint total = 0;             // the superset total weight
    while( ! cin.eof() )
  {
    uint value;
    if( cin >> value && ! cin.eof() )
      w.push_back( value );
  }

    W = w.front();
    w.erase( w.begin() );
    // instantiate the include vector to false
    for( uint k = 0; k <= w.size(); k++ )
        include.push_back(0);
    // calculate the superset total
    for( uint k = 0; k <= w.size()-1; k++ )
        total += w.at(k);
    // calculate the sum of subsets accordig to CL argument
    sum_of_subsets( index, weight, total, include, w, W );

    // report success   
    return 0;
}    

.

////////// Function Bodies ///////////
void sum_of_subsets( uint index, 
                     uint weight, 
                     uint total, 
                     vector<bool> &include, 
                     vector<uint> &w, 
                     uint W )
{    
    cout << "inside sumb_of_subsets" << endl;
    if( promising(index, weight, W, w, total) )
    {   
        cout << "promising is true, continue" << endl;
        if( weight == W )
        {   
            for( uint k = 0; k <= index; k++ )
            {
                if(include.at(k))
                    cout << w.at(k) << " ";;
            }
            cout << endl;
        }
        else
        {
            include.at(index + 1) = 1;
            cout << "index1 = " << index << endl;
            sum_of_subsets( index + 1, 
                            weight + w.at(index + 1 ), 
                            total - w.at(index + 1),
                            include, w, W ) ;
            include.at(index + 1) = 0;
            cout << "index2 = " << index << endl;
            sum_of_subsets( index + 1, 
                            weight, 
                            total - w.at(index + 1),
                            include, w, W );
        }
    }
}

.

bool promising ( uint index, 
                 uint weight, 
                 uint W, 
                 vector<uint> w,
                 uint total )
{    
    cout << "inside promising" << endl;
    cout << "W = " << W << endl;
    cout << "weight = " << weight << endl;
    return ( weight + total >= W )
         && ( (weight == W) || (weight + w.at(index+1) <= W));
}

Answer 1

This error:

terminate called after throwing an instance of 'std::out_of_range'
what(): vector::_M_range_check

Suggests that your debug version of vector is throwing an exception, and nothing catches it. When this happens, the program immediately terminates without unwinding the stack, which makes debugging harder.

Change to this:

// calculate the sum of subsets accordig to CL argument
try
{
  sum_of_subsets( index, weight, total, include, w, W );
}
catch (...)
{
  cout << "put breakpoint here!" << endl;
}

Add a breakpoint in the catch, and check the backtrace to see what part of your code went wrong.