Suggestion for better coding or better algorithm replacing the recursive multithread

Question

I made this code to solve this problem:

"For a give number (NUM), find the number of ordered sequences of numbers out of {1,2,3,5,7,11,14,23} so that the sum of the numbers in the sequence equals to the given number. (1. The order that each number appears in the sequence matters - counted as different sequences, 2. Same numbers are allowed to appear more than once in a given sequence)"

The original problem is a bit more complicated but I simplified to ask this question, as I get the same error message anyway.

My code is:

#include <thread>
#include <vector>
#define DIM     8
#define NUM     30   // This can be 300 for DIM of 16

long val[8] = {1,2,3,5,7,11,14,23}; // This is for DIM of 8
// Example for DIM of 16:
// long val[16] = {1,2,3,5,7,11,14,23,34,45,67,88,142,301,431,547};

int main()
{
        void sub(long, long*, int);
        long sum;

        sub(NUM, &sum, 0);
        printf("%d\n", sum);
}

void sub(long in, long *sum, int level)
{
        if(in < 0)
                *sum = 0;
        else if(in == 0)
                *sum = 1;
        else
        {
                std::vector<std::thread> th;
                th.reserve(DIM);
                int i;
                long psum[DIM];

                *sum = 0;
                for(i=0; i<DIM; i++)
                        th[i] = std::thread(sub, in - val[i], &psum[i], level+1);
                for(i=0; i<DIM; i++)
                        th[i].join();
                for(i=0; i<DIM; i++)
                        *sum += psum[i];
        }
}

But I get this error message:

terminate called without an active exception
Abort(coredump)

or sometimes

terminate called without an active exception
terminate called recursively
Abort(coredump)

I searched and found some questions relative to this error message including this that has exactly same subject to my question. However, I am wondering why I get this although I did join the threads (I think). I should also say that I am almost a dummy to the multi-thread programming. This is my first multi-thread code. I tried a non-multi-thread version of the code but it took forever to finish for DIM > 15.

Additional info are:

1. For a smaller NUM (e.g. 3), the code finishes with a correction answer (i.e. 4).
2. My g++ version seems to be 8.5.0
3. I compiled as 'g++ -pthread file.cpp'
4. I tried to clear() or std::terminate() or detach(), etc., but didn't get any luck.

Thanks for any help.

---

I changed the subject from asking for error fix into inclusion of suggestion for better algorithm, as I realized that what I need is probably a better algorithm to reduce the run time. (The example of DIM=16 and NUM=300 is still running for more than an hour. The original problem is DIM=20...).

Answer 1

You can do it by dynamic programming, but you have to watch out for overflow.

Let A[n] be the number of sequences for which the sum is n. Initialise it to 0. Then, for each n from 0 to target consider all the elements e in your collection. There are only two cases: either e is equal to n (in which case just add 1 to A[n]) or the A[n-e] previous sequences can be added to the tally A[n] (provided e < n).

The number of sequences can grow rapidly. I think the DIM=16, NUM=300 case will actually overflow an unsigned long long.

#include <iostream>
#include <vector>
#include <limits>
#include <cstdlib>
using namespace std;

const unsigned long long MAX = numeric_limits<unsigned long long>::max();

unsigned long long targetSum( const vector<int> &values, int target )     // all values assumed positive
{
   vector<unsigned long long> A( 1 + target, 0 );
   vector<bool> overflow( 1 + target, false );                            // is current sum overflowing?

   for ( int n = 0; n <= target; n++ )
   {
      for ( int e : values )
      {
         int toAdd = 0;
         if      ( e == n ) toAdd = 1;
         else if ( e < n  ) { toAdd = A[n-e];   overflow[n] = overflow[n] || overflow[n-e]; }

         if ( A[n] > MAX - toAdd ) overflow[n] = true;
         else                      A[n] += toAdd;
      }
   }

   if ( overflow[target] )   // frequency was made up of tallies which overflowed at some point
   {
      cout << "Overflow";
      exit(1);
   }

   return A[target];
}

//======================================================================

int main()
{
   cout << targetSum( { 1, 2, 3, 5, 7, 11, 14, 23 }, 5  ) << '\n';
   cout << targetSum( { 1, 2, 3, 5, 7, 11, 14, 23 }, 30 ) << '\n';
   cout << targetSum( { 1, 2, 3, 5, 7, 11, 14, 23, 34, 45, 67, 88, 142, 301, 431, 547 }, 300 ) << '\n';
}

Output (final case overflows):

14
131292855
Overflow