Pythonで全探索により部分和問題を解く

問題（蟻本 P.34）

整数a1, a2, ...., anが与えられます。その中からいくつか選び、その和をちょうどkにすることができるかどうかを判定しなさい。

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

#判定用の変数
cnt = 0

#全探索
for i in range(1<<len(a)):
    l = []
    for j in range(len(a)):
        if (i>>j & 1) == 1:
            l.append(a[j])
    if sum(l) == k:
        cnt += 1
print('Yes' if cnt>=1 else 'No')