kidtest.php

<?php

findsum(array(6,5,4,3,2,1),3);
findsum(array(6,5,4,3,2,1),5);
findsum(array(6,5,4,3,2,1),7);
findsum(array(6,5,4,3,2,1),1);
findsum(array(6,5,4,3,2,1),9);
findsum(array(6,5,4,3,2,1),11);

findsum(array(1,2,3,4,5,6,7,8),9);
findsum(array(12,3,4,5,6,7,8),9);


function findsum($numbers, $targetsum) {
    $sums = getsums($numbers);
    $rv = array();
    foreach ($sums as $sum) {
        if ($sum[1] == $targetsum) {
            $rv[] = $sum[0];
        }
    }
    echo "--------------------- (".join(',',$numbers).") -> $targetsum ----------\n";
    echo join("\n",$rv)."\n";
}


function getsums($numbers) {
    if (empty($numbers)) {
        return array(0);
    }
    $firstnumber = array_shift($numbers);
    $sums = getsums($numbers);
    $rv = array();
    foreach ($sums as $sum) {
        $rv[] = array("+$firstnumber".$sum[0], $firstnumber + $sum[1]);
        $rv[] = array("-$firstnumber".$sum[0], -$firstnumber + $sum[1]);
    }
    return $rv;
}