## Quick PHP Script to find values that add to a specified total

Posted on December 14th, 2012 in General by Brandon

I’ve had need for this on several occasions, and never come up with a decent solution until now. The problem happens for me most frequently when dealing with a group of transactions, and I need to find a subset of them that add up to a specific amount.

My data might look like this:

```+----+--------+
| id | total  |
+----+--------+
|  1 |    1.6 |
|  2 |    0.8 |
|  3 |  16.25 |
.........
| 50 |      5 |
| 51 |    2.5 |
| 52 |     29 |
| 53 |    3.5 |
+----+--------+
```

And I need to find some combination of those that add up to a certain amount. I put together this quick recursive script that comes up with a solution:

```\$available = array(
1 => 1.6,
2 => 0.8,
3 => 16.25,
.....
50 => 5,
51 => 2.5,
52 => 29,
53 => 3.5,
);

function findCombination(\$count_needed, \$amount_needed, \$remaining)
{
if (\$count_needed < 0) return false;

foreach (\$remaining as \$id => \$this_amount) {
if (\$count_needed == 1 && \$this_amount == \$amount_needed) {
echo "Found: {\$id} for {\$amount_needed}\n";
return true;
} else {
unset(\$remaining[\$id]);
\$correct = findCombination(\$count_needed - 1, \$amount_needed - \$this_amount, \$remaining);
if (\$correct) {
echo "Found: {\$id} for {\$this_amount}\n";
return true;
}
}

}
return false;
}
\$count_needed = 9;
\$amount_needed = 418;
findCombination(\$count_needed, \$amount_needed, \$available);
```

This will output something like:

```Looking for 9 transactions totaling 418
Found: 38 for 59
Found: 37 for 45.5
Found: 36 for 34.75
Found: 33 for 44.75
Found: 31 for 57.75
Found: 30 for 48
Found: 26 for 23.5
Found: 22 for 2.5
Found: 20 for 102.25
```