# include <stdbool.h>
# include <stdio.h>
# include <stdlib.h>
# include <time.h>

# include "subset_sum_backtrack.h"

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

/******************************************************************************/

int main ( )

/******************************************************************************/
/*
  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 ( );
  printf ( "\n" );
  printf ( "subset_sum_backtrack_test()::\n" );
  printf ( "  C version\n" );
  printf ( "  Test subset_sum_backtrack().\n" );

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

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

void subset_sum_backtrack_tests ( )

/******************************************************************************/
/*
  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 };

  printf ( "\n" );
  printf ( "subset_sum_backtrack_tests():\n" );
  printf ( "  subset_sum_backtrack_test() solves the subset sum problem\n" );
  printf ( "  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;
}
/******************************************************************************/

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

/******************************************************************************/
/*
  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

  Input:

    int S, the desired sum.

    int N, the number of values.

    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;

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

  more = false;
  u = ( int * ) malloc ( n * sizeof ( int ) );
  for ( i = 0; i < n; i++ )
  {
    u[i] = 0;
  }
  t = -1;
  
  printf ( "\n" );
  printf ( "  Desired sum S = %d\n", s );
  printf ( "  Number of targets = %d\n", n );
  printf ( "  Targets:" );
  for ( i = 0; i < n; i++ )
  {
    printf ( " %d", v[i] );
  }
  printf ( "\n" );
  printf ( "\n" );

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

  return;
}

/******************************************************************************/

void timestamp ( )

/******************************************************************************/
/*
  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:

    24 September 2003

  Author:

    John Burkardt
*/
{
# define TIME_SIZE 40

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

  now = time ( NULL );
  tm = localtime ( &now );

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

  fprintf ( stdout, "%s\n", time_buffer );

  return;
# undef TIME_SIZE
}