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

# include "subset_sum_backtrack.h"

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

void subset_sum_backtrack ( int s, int n, int v[], bool *more, int u[], int *t )
 
/******************************************************************************/
/*
  Purpose:
  
    subset_sum_backtrack() seeks, one at a time, subsets of V that sum to S.

  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.

    bool *MORE, should be set to FALSE before the first call.

    int U[N], should be set to 0 before the first call. 

    int *T, should be set to -1 before the first call.  

  Output:

    bool *MORE: MORE is TRUE if a solution is being returned,
    and FALSE if there are no more solutions.

    int U[N]: if MORE is TRUE, U indexes the selected entries
    of V that form a solution.

    int *T: if MORE is true, T is the highest index of the selected 
    values, although this is of little interest to the user.
*/
{
  int i;
  int su;
  int told;

  if ( ! *more )
  {
    *t = -1;
    for ( i = 0; i < n; i++ )
    {
      u[i] = 0;
    }
  }
  else
  {
    *more = false;
    u[*t] = 0;
/*
  Backup to previous 1.
*/
    told = *t;
    *t = -1;
  
    for ( i = told - 1; 0 <= i; i-- )
    {
      if ( u[i] == 1 )
      {
        *t = i;
        break;
      }
    }
    
    if ( *t < 0 )
    {
      return;
    }

    u[*t] = 0;
    *t = *t + 1;
    u[*t] = 1;   
  }
    
  while ( true )
  {
    su = 0;
    for ( i = 0; i < n; i++ )
    {
      su = su + u[i] * v[i];
    }
  
    if ( su < s && *t < n - 1 )
    {
      *t = *t + 1;
      u[*t] = 1;
    }
    else
    {
      if ( su == s )
      {
        *more = true;
        return;
      }

      u[*t] = 0;
/*
  Backup to previous 1.
*/
      told = *t;
      *t = -1;
  
      for ( i = told - 1; 0 <= i; i-- )
      {
        if ( u[i] == 1 )
        {
          *t = i;
          break;
        }
      }
      
      if ( *t < 0 )
      {
        break;
      }

      u[*t] = 0;
      *t = *t + 1;
      u[*t] = 1; 
    }
  }

  return;
}