# [PHP] Find all combinations of numbers

```
Hi,```
```
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:

\$number[0]['id']=5;
\$number[0]['number']=500;
\$number[1]['id']=7;
\$number[1]['number']=500;
\$number[2]['id']=23;
\$number[2]['number']=750;
\$number[3]['id']=3;
\$number[3]['number']=1500;

\$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;

5
7
23
5&7
5&23
7&23

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!

Thanks,
Michael.

-~=**=~--~=**=~--~=**=~--~=**=~--~=**=~--~=**=~--~=**=~--~=**=~--~=**=~-

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) &&
!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"

-~=**=~--~=**=~--~=**=~--~=**=~--~=**=~--~=**=~--~=**=~--~=**=~--~=**=~-

--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

```