function i4vec_backtrack_test ( )

%*****************************************************************************80
%
%% i4vec_backtrack_test() tests i4vec_backtrack().
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    16 June 2015
%
%  Author:
%
%    John Burkardt
%
  fprintf ( 1, '\n' );
  fprintf ( 1, 'i4vec_backtrack_test():\n' );
  fprintf ( 1, '  i4vec_backtrack() uses backtracking, seeking a vector X of\n' );
  fprintf ( 1, '  N values which satisfies some condition.\n' );

  fprintf ( 1, '\n' );
  fprintf ( 1, '  In this demonstration, we have 8 integers W(I).\n' );
  fprintf ( 1, '  We seek all subsets that sum to 53.\n' );
  fprintf ( 1, '  X(I) is 0 or 1 if the entry is skipped or used.\n' );
  fprintf ( 1, '\n' );

  n = 8;
  maxstack = 100;
  stacks = zeros ( maxstack, 1 );
  x = zeros ( n );
  indx = 0;
  k = 1;
  nstack = 0;
  ncan = zeros ( n, 1 );

  w = [ 15, 22, 14, 26, 32, 9, 16, 8 ];
  t = 53;

  found_num = 0;

  while ( true )

    [ x, indx, k, nstack, stacks, ncan ] = i4vec_backtrack ( n, maxstack, ...
      x, indx, k, nstack, stacks, ncan );

    if ( indx == 1 )

      found_num = found_num + 1;
      fprintf ( 1, '  %2d   ', found_num );

      total = 0.0;
      for i = 1 : n
        if ( x(i) == 1 )
          total = total + w(i);
        end
      end
      fprintf ( 1, '  %2d:  ', total );

      for i = 1 : n
        if ( x(i) == 1 )
          fprintf ( 1, '  %d', w(i) )
        end
      end
      fprintf ( 1, '\n' );
%
%  Given that we've chose X(1:K-1), what are our choices for X(K)?
%
%    if T < TOTAL, 
%      no choices
%    if T = TOTAL, 
%      X(K) = 0
%    if T > TOTAL and K < N, 
%      X(k) = 0
%      If ( W(K)+TOTAL <= T ) X(K) = 1
%    If T > TOTAL and K = N,
%      If ( W(K) + TOTAL) = T ) X(K) = 1
%
    elseif ( indx == 2 )

      total = 0.0;
      for i = 1 : k - 1
        if ( x(i) == 1 )
          total = total + w(i);
        end
      end

      if ( t < total )

        ncan(k) = 0

      elseif ( t == total )

        ncan(k) = ncan(k) + 1;
        nstack = nstack + 1;
        stacks(nstack) = 0;

      elseif ( total < t & k < n )

        ncan(k) = ncan(k) + 1;
        nstack = nstack + 1;
        stacks(nstack) = 0;

        if ( total + w(k) <= t )
          ncan(k) = ncan(k) + 1;
          nstack = nstack + 1;
          stacks(nstack) = 1;
        end

      elseif ( total < t & k == n )

        if ( total + w(k) == t )
          ncan(k) = ncan(k) + 1;
          nstack = nstack + 1;
          stacks(nstack) = 1;
        end

      end

    else

      fprintf ( 1, '\n' );
      fprintf ( 1, '  Done!\n' );
      break;

    end

  end

  return
end
