ALDS_5_A – 総当たり

以下のように、単純な総当たりだとTLE

import sys

def solve(a,l,ans):
    for i in range(2 ** l):
        cnt = 0
        for j in range(l):
            if (i >> j) & 1:
                cnt += a[j]
                if cnt == ans:
                    return "yes"
    
    return "no"

l = int(sys.stdin.readline().strip())
a =  list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline().strip())
q =  list(map(int, sys.stdin.readline().split()))


for ans in q:
    print(solve(a,l,ans))

ALDS1 5A 総当たり

この記事で使うアルゴリズム全探索はじめにカテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。全問題の一覧はこちらです問題

を参照し、

import sys
from itertools import product

l = int(sys.stdin.readline().strip())
a =  list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline().strip())
q =  list(map(int, sys.stdin.readline().split()))

create = [0] * 40001


for pro in product((0, 1), repeat=l):
    cnt = 0
    for j in range(l):
        if pro[j]:
            cnt += a[j]
    create[cnt] = 1

for s in q:
    if create[s]:
        print("yes")
    else:
        print("no")

にするとACした。