1時間以内に解けなければプログラマ失格となってしまう5つの問題（5）

ちょっと前に話題になっていたこちらの問題5をPHPでやってみた。

Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, ..., 9 (in this order) such that the result is always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.

1, 2, ..., 9の順で並んだ数字の間に"＋"か"ー"か"何もナシ"かを入れて、合計が100になる組み合わせを列挙せよ、という問題。

書いてみたコードはこんな感じ

<?php
define('TARGET_SUM',100);
$numbers = array(1,2,3,4,5,6,7,8,9);

function culc($numbers, $siki=""){
    $siki .= array_shift($numbers);
    if(!empty($numbers)){
       culc($numbers, $siki."+");
       culc($numbers, $siki."-");
       culc($numbers, $siki);
    }else{
        eval('$sum='.$siki.';');
        if($sum == TARGET_SUM){
            echo $siki."=".$sum."\n";
        }
    }
}

culc($numbers);

再起ですべての式を列挙してevalで評価してます。
関数名が適当なのはご愛嬌ということで。

ちなみに結果はこんな感じ。

$ php toi5.php
1+2+3-4+5+6+78+9=100
1+2+34-5+67-8+9=100
1+23-4+5+6+78-9=100
1+23-4+56+7+8+9=100
12+3+4+5-6-7+89=100
12+3-4+5+67+8+9=100
12-3-4+5-6+7+89=100
123+4-5+67-89=100
123+45-67+8-9=100
123-4-5-6-7+8-9=100
123-45-67+89=100