もとの問題はこちら: Five programming problems every Software Engineer should be able to solve in less than 1 hour
日本語訳：1時間以内に解けなければプログラマ失格となってしまう5つの問題
このうちの問題５にPythonで挑戦してみました。
問題５： 1,2,…,9の数をこの順序で、”+”、”-“、またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる。
考え方
関数 f(n, M) を、1 ~ n の数字を使って計算結果が M となる方法をすべて返す関数として定義します（戻り値はリスト）。すると、求めたい答えは f(9, 100)です。
まず、そのままで計算が成り立つ場合（例：n=3, M=123）、M を文字列にしたものが答えの１つになります。さらに、f(n, M)は、より小さな n に分解することができます。再帰的に分解を繰り返していくことで、すべての計算方法を見つけることができます。
#例：f(3, 9) の場合
まず、そのままでは式が成り立ちません（123 ≠ 9）。
f(3, 9)は次の４通りに分解できます（一般に、(n-1)*2通りの分解法があります）。
f(2, 6) "+3"
f(2, 12) "-3"
f(1, -14) "+23"
f(1, 32) "-23"
このうち、f(1, -14), f(1, 32) についてはこれ以上分解できず、またそのままで式が成立しないので不適。
f(2, 6) は、さらに f(1, 5) "+1" と f(1, 7) "-1" に分解できますが、いずれも式が成立しません。
f(2, 12) は、そのままで式が成立するパターンですので、"12"が１つの解です。
また、f(1, 11) "+1" と f(1, 13) "-1" に分解できますが、いずれも不適。
したがって、"12-3"が唯一の解として求められます。
f(9, 100) を計算すると、出題者の提示した１１パターン（Solution to Problem 5）と同じ解がでています。
ただし、こういう再帰的な関数の使い方は多少気持ち悪くて、Pythonの場合は再帰の深度が1000を越えると実行エラーになります（参照）。この例では、深さが９を超えることはないので平気です。
また、解答例では１〜９以外の数字列にも対応できる仕組みになっていましたが、僕の方法ではそれができないのが弱い。
def fun5(n, M):
digits = "123456789"[0:n]
out = []
if int(digits) == M:
out += [ digits ]
for i in xrange(1, n):
out += map(lambda z: z + "+" + digits[-i:n], fun5(n - i, M - int(digits[-i:n])) )
out += map(lambda z: z + "-" + digits[-i:n], fun5(n - i, M + int(digits[-i:n])) )
return out
print fun5(2, 3)
print fun5(5, 168)
print fun5(9, 100)
#['1+2']
#['123+45']
#['1+23-4+56+7+8+9', '12+3-4+5+67+8+9', '1+2+34-5+67-8+9', '1+2+3-4+5+6+78+9', '123-4-5-6-7+8-9', '123+45-67+8-9', '1+23-4+5+6+78-9', '12-3-4+5-6+7+89', '12+3+4+5-6-7+89', '123-45-67+89', '123+4-5+67-89']