Pythonで理解する蟻本「2-1 部分和問題」(p.34) - クルトンのプログラミング教室

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-1 部分和問題」(p.34)
のコードをPythonで書き直したものとなっています。

入力
入力例
再帰回数の上限
解答

入力

$n\,k\\a_1\,…\,a_n$

入力例

4 13
1 2 4 7

再帰回数の上限

Pythonでは再帰回数の上限が設定されています。
そのため、競技プログラミングにおいては再帰関数の上限を十分大きい値に設定し直す必要があります。（AtCoderでは上限回数を超えると「Runtime Error」になります）

再帰回数の上限は

import sys
sys.setrecursionlimit(4100000)

で設定し直すことができます。

このエラーは初見では原因が分かりづらく、再帰回数に上限があることを知らなければエラーの原因を調べるのに大幅に時間を溶かすことになります。

この機会にしっかりと覚えておきましょう。

解答

# 再帰回数の上限を設定する
import sys
sys.setrecursionlimit(4100000)

# 入力
n, k = map(int,input().split())
a = list(map(int,input().split()))

# iまででSUMを作って、残りi以降を調べる
def dfs(i, SUM):
    # n個決め終わったら、今までの和SUMがkと等しいかを返す
    if i == n:
        return SUM == k
    
    # a[i]を使わない場合
    if dfs(i + 1, SUM):
        return True
    
    # a[i]を使う場合
    if dfs(i + 1, SUM + a[i]):
        return True
    
    # a[i]を使う使わないに拘わらずkが作れないのでfalseを返す
    return False

if dfs(0, 0):
    print("Yes")
else:
    print("No")