function [ x_num, x ] = i4mat_rref_solve_binary_nz ( m, n, nz, a, b )

%*****************************************************************************80
%
%% I4MAT_RREF_SOLVE_BINARY_NZ seeks binary solutions of an IRREF system.
%
%  Discussion:
%
%    An MxN linear system A*x = b is considered.
%
%    The matrix A and right hand side B are assumed to have been converted
%    to integer row-reduced echelon form (IRREF).
%
%    In order to solve a particular combinatorial problem, only binary
%    solutions x are of interest; that is, each entry of x is either 0 or 1.
%
%    Moreover, we know that exactly NZ of the variables are 1.
%
%    The solution procedure involves two steps:
%    * assign each free variable a value of 0 or 1, but never assign more
%      that NZ nonzeroes;
%    * solve for the dependent variables.
%
%    We consider every possible assignment of free variables, and we save
%    the solutions in which all the variables take on only 0 or 1 values.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    08 September 2018
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    integer M, N, the number of rows and columns.
%
%    integer NZ, the number of nonzeros required in any binary
%    solution.
%
%    integer A(M,N), the IRREF matrix to be analyzed. 
%
%    integer B(M), the right hand side.
%
%  Output:
%
%    integer X_NUM, the number of binary solutions discovered.
%    Note that there may be no binary solutions at all.
%
%    integer X(N,X_NUM), the binary solutions, if any.
%

%
%  Augment the original linear system to the NxN system A2 x = B2.
%
  [ a2, b2, incon, freedom_num, freedom ] = i4mat_rref_system ( m, n, a, b );
%
%  Initialize our list of solutions.
%
  x_num = 0;
  x = [];
%
%  If FREEDOM_NUM < 0, then the system is overdetermined and cannot be solved.
%
  if ( freedom_num < 0 )
    return
  end
%
%  There are FREEDOM_NUM degrees of freedom, each of which could be set to 1.
%  There must be NZ variables set to 1.
%  Consider setting NZ2 degrees of freedom to 1, where NZ2 is between 0
%  and the minimum of NZ and FREEDOM_NUM.
%
%  Choose every possible selection of NZ2 degrees of freedom, and solve
%  the system.
%
%  If the resulting solution is binary, then add it to the list.
%
  b_num = 0;

  for nz2 = 0 : min ( nz, freedom_num )

    done = true;
    free_sub = [];

    while ( true )

      [ free_sub, done ] = ksub_next4 ( freedom_num, nz2, free_sub, done );

      if ( done )
        break;
      end

      b3 = b2;
      b3(freedom(free_sub(1:nz2)),1) = 1;
      b_num = b_num + 1;

      y = i4mat_u_solve ( n, a2, b3 );

      if ( i4vec_is_binary ( n, y ) ) 
        x_num = x_num + 1;
        x(1:n,x_num) = y(1:n,1);
      end

    end

  end

  return
end
