function [ c, index ] = subset_sum_find ( w, t, r )

%*****************************************************************************80
%
%% SUBSET_SUM_FIND seeks a subset of a set that has a given sum.
%
%  Discussion:
%
%    This function tries to compute a target value as the sum of
%    a selected subset of a given set of weights.
%
%    This function works by brute force, that is, it tries every
%    possible subset to see if it sums to the desired value.
%
%    Given N weights, every possible selection can be described by
%    one of the N-digit binary numbers from 0 to 2^N-1.
%
%    This function includes a range, which allows the user to
%    control which subsets are to be checked.  Thus, if there are
%    N weights, specifying a range of [ 0, 2^N-1] indicates that
%    all subsets should be checked.  On the other hand, this full
%    range could be broken down into smaller subranges, each of
%    which could be checked independently.
%
%    It is possible that, in the given range, there may be multiple
%    solutions of the problem.  This function will only return
%    one such solution, if found.  However, the function may be called
%    again, with an appropriate restriction of the range, to continue
%    the search for other solutions.
%
%  Example:
%
%    w = [ 1, 2, 4, 8, 16, 32 ];
%    t = 22;
%    r = [ 0, 2^6 - 1 ];
%
%    [ c, index ] = subset_sum ( w, t, r )
%
%    c = [ 2, 3, 5 ]
%    index = 22
%
%  Licensing:
%
%    This code is distributed under the GNU LGPL license.
%
%  Modified:
%
%    14 December 2009
%
%  Author:
%
%    John Burkardt
%
%  Parameters:
%
%    Input, integer W(N), a set of weights.  The length of this
%    array must be no more than 31.
%
%    Input, integer T, the target value.
%
%    Input, integer R(2), the lower and upper limits to be searched.
%    If this argument is omitted, the entire range, [0, 2^N-1 ] will
%    be searched.
%
%    Output, integer C(*), the indices of the weights used to
%    make the combination.  This array is empty if no solution was found.
%    Otherwise, the list of weights used to form the sum is
%    W(C).
%
%    Output, integer INDEX, the index, between [ R(1), R(2) ], of the solution
%    that was found, or an empty value if no solution was found.
%    If a solution was found, you might call again for further solutions
%    in the unchecked portion of the range, using the range
%    [ INDEX+1, R(2) ].
%
  c = [];
  index = [];
%
%  Using a single integer to track the subsets only works if the number
%  of objects is small enough.  MATLAB can pack no more than 31 bits of
%  information into a nonnegative integer.
%
  if ( nargin < 1 )
    w = input ( 1, '  Enter the vector of weights [ w(1), w(2), ..., w(n)]: ' );
  end

  n = length ( w );

  if ( 31 < n )
    fprintf ( 1, '\n' );
    fprintf ( 1, 'SUBSET_SUM_FIND - Fatal error!\n' );
    fprintf ( 1, '  This function is restricted to N <= 31.\n' );
    error ( 'SUBSET_SUM_FIND - Fatal error!' );
  end

  if ( nargin < 2 )
    t = input ( '  Enter the target value T: ' );
  end
%
%  Make sure the range is reasonable.
%
  if ( nargin < 3 )
    r(1) = 0;
    r(2) = 2^n - 1;
  else
    r(1) = max ( r(1), 0 );
    r(2) = min ( r(2), 2^n - 1 );
  end

  fprintf ( 1, '\n' )
  fprintf ( 1, '  Searching indices %d through %d\n', r(1), r(2) );
%
%  Run through the range.
%
  for index = r(1) : r(2)
%
%  Convert INDEX into vector of indices in W.
%
    c = find ( bitget ( index, 1:n ) );
%
%  If the sum of those weights matches the target, return combination.
%
    if ( sum ( w(c) ) == t )
      return
    end

  end

  index = [];

  return
end