Month: December 2012

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