编写一个在1,2,...,9（顺序不能变）数字之间插入+或者-或什么都不插入，使得计算结构总是100的程序，并输出所有的可能性。

Question

        面试php岗位的时候遇到的一道面试题：
 
        编写一个在1,2,...,9（顺序不能变）数字之间插入+或者-或什么都不插入，使得计算结构总是100的程序，并输出所有的可能性。例如：1+2+34-5+67-8+9=100　　还没想好怎么做，希望会做的朋友们给点帮助。

Answer 1

递归，很简单的foo();
print_r($res);function foo($n=1, $expr='') {
  $r = eval("return $expr;");
  if($r > 100) return;
  if($n == 9 && $r == 100) return save($expr);
  if(!$expr) $expr = $n;
  if($n < 9) {
    foo($n+1, $expr . ($n+1));
    foo($n+1, $expr . '+' . ($n+1));
    foo($n+1, $expr . '-' . ($n+1));
  }
}
function save($s) {
  global $res;
  $res[] = $s;
}
Array
(
    [0] => 12+3+4+5-6-7+89
    [1] => 12+3-4+5+67+8+9
    [2] => 12-3-4+5-6+7+89
    [3] => 1+23-4+56+7+8+9
    [4] => 1+2+34-5+67-8+9
    [5] => 1+2+3-4+5+6+78+9
)