function choose = subset_sum_brute ( n, weight, target )

%*****************************************************************************80
%
%% subset_sum_brute() 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.
%
%    It is possible that there may be multiple solutions of the problem.  
%    This function will only return the first solution found.
%
%  Example:
%
%    c = subset_sum_brute ( 6, [1 2 4 8 16 32], 22 )
%
%    c = [ 0 1 1 0 1 0 ]
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    01 July 2013
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    integer N, the number of weights.
%
%    integer WEIGHT(N), a set of weights.
%
%    integer TARGET, the target value.
%
%  Output:
%
%    integer CHOOSE(N), contains a 1 for each weight that is
%    chosen, 0 for weights not chosen.  If no solution was found,
%    all entries are -1.
%
  weight = weight(:);
%
%  Iterate through all possible combinations in the provided range.
%
  for i = 0 : 2^n - 1
%
%  Find the combination of weights represented by the current attempt.
%
    choose = i4_to_digits_binary ( i, n );
%
%  Sum the chosen weights.
%
    w_sum = choose(:)' * weight(:);
%
%  If the sum matches the target, return the combination.
%
    if ( w_sum == target )
      return
    end
    
  end

  choose(1:n) = -1;

  return
end

