The way I would tackle this is in several steps (and maybe combine them
Here goes - in pseudo code/point form

1. Find max
2. Find all array elements who's number in less than max
  2a. create a temp array that holds these indexes
3. Do the ol' nPr (or is it nCr?) thingo on the temp array, then using that
to refer the the actual array.

HTH (and it's not too confusing)

-----Original Message-----
From: Michael Benbow [mailto:[EMAIL PROTECTED]]
Sent: Wednesday, July 03, 2002 4:07 PM
Subject: [PHP] Find all combinations of numbers


I searched through the archives and found the following snippit of code
from Tim Converse from late 2000.  This is great, but does anyone know
how I can adapt this so I can return all values from a multidimensional
array?  I have an id number which corresponds to a record which I need
to revisit once I get all possible combinations (not just the max which
below gives us) and I do not want to lose the link between the id and
the number.  For instance:


$max is assigned the value 1350 in this example, so we know id 3 will be
eliminated off the bat.

What I need to get back are the combinations of ID's where their
corresponding number are less than or equal to value $max.  So in this
instance I might get something like;


I have spent about 40 hours in the last three days on this problem alone
and I can honestly say I am stuck.  You guys are my last hope.  Please
help a desperate man!



Tim's code:

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) &&
        $working_array[$possibly_new] = $candidate;
    if(($candidate <= $max) &&
      $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]);

// 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"


PHP General Mailing List (
To unsubscribe, visit:

PHP General Mailing List (
To unsubscribe, visit:

Reply via email to