AtCoder Beginner Contest 079 C を Python で解きたい

前提・実現したいこと

蟻本をやり初めまして，AtCoder 版！蟻本 (初級編)からAtCoder Beginner Contest 079 C を Python BFS で解きたいと思い，問題を解くソースコードを書いたのですが，エラーが表示されます。
string index out of range となりますが，なぜこうなるのかが分かりません。
問題を解くだけなら解けるのですが，BFSの勉強をしているのでBFSで解きたいです。このソースコードをどのように改善すればよいか，または根本的に間違っているのならどのようなソースコードを書けばいいのかを教えていただきたいです。

発生している問題・エラーメッセージ

Traceback (most recent call last):
  File "a.py", line 9, in <module>
    print(dfs(0, n[0]))
  File "a.py", line 7, in dfs
    return dfs(i+1, l + "+" + n[i+1]), dfs(i+1, l + "+" + "-" + n[i+1])
  File "a.py", line 7, in dfs
    return dfs(i+1, l + "+" + n[i+1]), dfs(i+1, l + "+" + "-" + n[i+1])
  File "a.py", line 7, in dfs
    return dfs(i+1, l + "+" + n[i+1]), dfs(i+1, l + "+" + "-" + n[i+1])
  [Previous line repeated 1 more time]
IndexError: string index out of range

該当のソースコード

Python
1n = input()
2
3def dfs(i, l):
4    if i == 3:
5        if sum(list(map(int, l.split("+")))) == 7:
6            return l
7    return dfs(i+1, l+"+"+n[i+1]), dfs(i+1, l+"+"+"-"+n[i+1])
8
9print(dfs(0, n[0]))

行動規範の内容に同意します

回答1件

ベストアンサー

オリジナルのコードだと終了するのは i==3 かつ組み立てた数式の答えが7 の場合のみになっています。
さらに、return dfs(+の場合), dfs(-の場合) とプラスマイナス両方のパタンをreturnしようとしているので、どこかでi==3の状態で n[i+1]にアクセスしようとして存在しないn[4]を読みにいってIndexErrorになっているのだと思います。
以下のように変更すればIndexErrorは出なくなると思います。

python
1n = input()
2
3def dfs(i, l):
4    if i == 3:
5        return l+'=7' if sum(list(map(int, l.split("+")))) == 7 else ''
6    return dfs(i+1, l+"+"+n[i+1]) or dfs(i+1, l+"+"+"-"+n[i+1])
7
8print(dfs(0, n[0]).replace('+-', '-'))  # 0290が 0+-2+9+0=7 のような答えになるので、 0-2+9+0=7 にする
9

もしくは、こんな感じで。

python
1n = input()
2
3def dfs(i, l):
4    if i == 3:
5        return l+'=7' if eval(l) == 7 else ''
6    return dfs(i+1, l+"+"+n[i+1]) or dfs(i+1, l+"-"+n[i+1])
7
8print(dfs(0, n[0])
9