Recursive function in php to reconcile credit card batches to an array of charges where the sum of a subset of charges matches the batch amount. Absurdly easy to "see" and do with your mind, getting it programmed was not easy at all.

reconcile.php

<?
	$charges=Array(
		 '2863996511' => 154.00 ,'2863879671' => 10.88
		,'2863992361' => 762.20 ,'2863858891' => 209.00
		,'2863898975' => 49.00  ,'2863856334' => 148.00
		,'2863894564' => 5.44   ,'2863367273' => -25.01
	); print_r($charges);
	$targets=Array(1302.63, 1327.64, 1322.20 );
	foreach( $targets as $batch ) {
		printf( "We seek combination of transId's to = $%-7.2f\n", $batch);
		$answer=reconcile( $batch, $charges );
		if( is_array($answer) )
			echo eval( "return ".implode("+",$answer).";" )."\nWIN!\n";
		else
			echo "Bust!\n";
	}	
		
// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- 
// recursive reconcile to find if a subset of a charges array matches our batch
function reconcile( $target, $arr ){
	if( count($arr) < 2 )
		return FALSE;
	$sum = eval( "return ".implode("+",$arr).";" );	// 154.00 + 10.88 + 762.20 + 209.00 + 49.00 + 148.00
	if($sum < $target) {
		$negatives=0;
		// add up the negatives and see if it's even possible to meet the target
		foreach( $arr as $id=>$amt )
			if( $amt < 0 )
				$negatives+=$amt;
		if($sum < ($target+$negatvies)) {
			// echo "Impossible for input array of charges ($$sum) to add up to $$target, bailing.  (line: ". __LINE__ .")\n";
			return FALSE;
		}
	}
	foreach( $arr as $id=>$amt ){
		if( abs($sum-$target-$amt) < .01 ) {
			echo ".  omit $id : ".$arr[$id]."\n";
			unset($arr[$id]); 
			return $arr; // return the array of the matched subset
		}
	}
	foreach( $arr as $id=>$amt ){
		$tmp=$arr;			// make copy of input array
		unset($tmp[$id]);	// get rid of this iteration's charge amount
		// call ourself to see if a subset of this subset matches
		$rtn = reconcile( $target, $tmp );
		if( is_array($rtn) ) {
			echo ".. omit $id : ".$arr[$id]."\n";
			return $rtn;	// return our subset of subset
		}
	}
	return FALSE;	// never found a match, sorry!
}


/*
	We seek combination of transId's to = $1302.63
	. omit 2863879671 : 10.88
	1302.63
	WIN!
	We seek combination of transId's to = $1327.64
	. omit 2863367273 : -25.01
	.. omit 2863879671 : 10.88
	1327.64
	WIN!
	We seek combination of transId's to = $1322.20
	. omit 2863367273 : -25.01
	.. omit 2863879671 : 10.88
	.. omit 2863894564 : 5.44
	1322.2
	WIN!
*/
?>