# include <cstdlib>
# include <ctime>
# include <iomanip>
# include <iostream>

using namespace std;

# include "subset_sum_backtrack.hpp"

int main ( );
void subset_sum_backtrack_test ( int s, int n, int v[] );
void subset_sum_backtrack_tests ( );
void timestamp ( );

//****************************************************************************80

int main ( )

//****************************************************************************80
//
//  Purpose:
//
//    subset_sum_backtrack_test() tests subset_sum_backtrack().
//
//  Licensing:
//
//    This code is distributed under the MIT license. 
//
//  Modified:
//
//    05 November 2022
//
//  Author:
//
//    John Burkardt
//
{
  timestamp ( );
  cout << "\n";
  cout << "subset_sum_backtrack_test():\n";
  cout << "  C++ version\n";
  cout << "  Test subset_sum_backtrack().\n";

  subset_sum_backtrack_tests ( );
//
//  Terminate.
//
  cout << "\n";
  cout << "subset_sum_backtrack_test():\n";
  cout << "  Normal end of execution.\n";
  cout << "\n";
  timestamp ( );

  return 0;
}
//****************************************************************************80

void subset_sum_backtrack_tests ( )

//****************************************************************************80
//
//  Purpose:
//
//    subset_sum_backtrack_tests() tests subset_sum_backtrack_test().
//
//  Licensing:
//
//    This code is distributed under the MIT license. 
//
//  Modified:
//
//    05 November 2022
//
//  Author:
//
//    John Burkardt
//
{
  int n;
  int s;
  static int v01[5] = { 1, 2, 3, 5, 7 };
  static int v02[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  static int v03[9] = { 1, 2, 3, 3, 5, 6, 7, 8, 9 };
  static int v04[5] = { 1, 2, 3, 5, 7 };
  static int v05[10] = { 267, 493, 869, 961, 1000, 1153, 1246, 1598, 1766, 1922 };

  cout << "\n";
  cout << "SUBSET_SUM_backtrack_TESTS:\n";
  cout << "  SUBSET_SUM_backtrack_TEST solves the subset sum problem\n";
  cout << "  for specific values of S, N and V.\n";
  
  s = 9;
  n = 5;
  subset_sum_backtrack_test ( s, n, v01 );
  
  s = 8;
  n = 9;
  subset_sum_backtrack_test ( s, n, v02 );
//
//  What happens with a repeated target?
//
  s = 8;
  n = 9;
  subset_sum_backtrack_test ( s, n, v03 );
//
//  What happens with a target that needs all the values?
//
  s = 18;
  n = 5;
  subset_sum_backtrack_test ( s, n, v04 );
//
//  A larger S.
//
  s = 5842;
  n = 10;
  subset_sum_backtrack_test ( s, n, v05 );
  
  return;
}
//****************************************************************************80

void subset_sum_backtrack_test ( int s, int n, int v[] )

//****************************************************************************80
//
//  Purpose:
//
//    subset_sum_backtrack_test() tests subset_sum_backtrack().
//
//  Licensing:
//
//    This code is distributed under the MIT license. 
//
//  Modified:
//
//    05 November 2022
//
//  Author:
//
//    John Burkardt
//
//  Parameters:
//
//    Input, int S, the desired sum.
//
//    Input, int N, the number of values.
//
//    Input, int V[N], the values.
//    These must be nonnegative, and sorted in ascending order.  
//    Duplicate values are allowed.
//
{
  int i;
  int k;
  bool more;
  bool plus;
  int t;
  int *u;

  cout << "\n";
  cout << "subset_sum_backtrack_test():\n";
  cout << "  subset_sum_backtrack() finds the next subset of the values V\n";
  cout << "  which sum to the desired total S.\n";

  more = false;
  u = new int[n];
  for ( i = 0; i < n; i++ )
  {
    u[i] = 0;
  }
  t = -1;
  
  cout << "\n";
  cout << "  Desired sum S = " << s << "\n";
  cout << "  Number of targets = " << n << "\n";
  cout << "  Targets:";
  for ( i = 0; i < n; i++ )
  {
    cout << " " << v[i];
  }
  cout << "\n";
  cout << "\n";

  k = 0;
  
  while ( true )
  {
    subset_sum_backtrack ( s, n, v, more, u, t );
    if ( ! more )
    {
      break;
    }
    k = k + 1;
    cout << "  " << k << ":  " << s << " =";
    plus = false;
    for ( i = 0; i < n; i++ )
    {
      if ( u[i] != 0 )
      {
        if ( plus )
        {
          cout << " +";
        }
        cout << " " << v[i];
        plus = true;
      }
    }
    cout << "\n";
  }
   
  delete [] u;

  return;
}
//****************************************************************************80

void timestamp ( )

//****************************************************************************80
//
//  Purpose:
//
//    timestamp() prints the current YMDHMS date as a time stamp.
//
//  Example:
//
//    31 May 2001 09:45:54 AM
//
//  Licensing:
//
//    This code is distributed under the MIT license. 
//
//  Modified:
//
//    08 July 2009
//
//  Author:
//
//    John Burkardt
//
{
# define TIME_SIZE 40

  static char time_buffer[TIME_SIZE];
  const struct std::tm *tm_ptr;
  std::time_t now;

  now = std::time ( NULL );
  tm_ptr = std::localtime ( &now );

  std::strftime ( time_buffer, TIME_SIZE, "%d %B %Y %I:%M:%S %p", tm_ptr );

  std::cout << time_buffer << "\n";

  return;
# undef TIME_SIZE
}