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

問題（蟻本 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')