function maximum_subset_sum ($max, $candidate_array) {
$working_array = array();
while ($next = each($candidate_array)) {
$candidate = $next['value'];
$sums_to_date = array_keys($working_array);
while ($marked_sum = each($sums_to_date)) {
$known_sum = $marked_sum['value'];
$possibly_new = $known_sum + $candidate;
if(($possibly_new <= $max) &&
!IsSet($working_array[$possibly_new])){
$working_array[$possibly_new] = $candidate;
}
}
if(($candidate <= $max) &&
!IsSet($working_array[$candidate])){
$working_array[$candidate] = $candidate;
}
}
$max_sum = max(array_keys($working_array));
$return_array = array($working_array[$max_sum]);
while ($max_sum != $working_array[$max_sum]) {
$max_sum = $max_sum - $working_array[$max_sum];
array_push($return_array, $working_array[$max_sum]);
}
return($return_array);
}

// example use
$best_sum = maximum_subset_sum(40, array(39,23,19,14,9,5,3,2,1));
print("Largest sum is " . array_pop($best_sum));
while ($value = array_pop($best_sum)) {
print(" + $value");
} // will print "Best sum is 23 + 14 + 3"