# include <cstdlib>

using namespace std;

# include "subset_sum_backtrack.hpp"

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

void subset_sum_backtrack ( int s, int n, int v[], bool &more, int u[], int &t )
 
//****************************************************************************80
//
//  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:
//
//    15 July 2017
//
//  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.
//
//    Input/output, bool &MORE, should be set to FALSE before the first call.
//    Thereafter, on output, MORE is TRUE if a solution is being returned,
//    and FALSE if there are no more solutions.
//
//    Input/output, int U[N], should be set to 0 before the 
//    first call.  On output with MORE TRUE, U indexes the selected entries
//    of V that form a solution.
//
//    Input/output, int &T, should be set to -1 before the first 
//    call.  On output, 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;

    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;

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