ARC061 C - たくさんの数式をPythonで実装

目的

AtCoder 版！蟻本 (初級編)で「たくさんの数式」で躓いたので理解したことを備忘録として残す。

問題

1 以上 9 以下の数字のみからなる文字列Sが与えられます。 この文字列の中で、あなたはこれら文字と文字の間のうち、いくつかの場所に + を入れることができます。 一つも入れなくてもかまいません。 ただし、+ が連続してはいけません。

このようにして出来る全ての文字列を数式とみなし、和を計算することができます。

ありうる全ての数式の値を計算し、その合計を出力してください。

s = input()
n = len(s)

def dfs(i, f):
    if i == (n - 1):
        return sum(list(map(int, f.split("+"))))
    return dfs(i + 1, f + s[i + 1]) + dfs(i + 1, f + "+" + s[i + 1])

print(dfs(0, s[0]))

実装内容

dfs(0, s[0]) を呼び出した時の様子を図示してみます。s = "125"なので、図ではs[0]を文字列の"1"として表してます。同様に、s[1]を文字列の"2"、s[2]を文字列の"5"として表してます。再帰的にdfsを呼び出すことで、総和を得ていることがわかります。

参照