Problem:


Exhaustive Search

Write a program which reads a sequence A of n elements and an integer M, and outputs "yes" if you can make M by adding elements in A, otherwise "no". You can use an element only once.

You are given the sequence A and q questions where each question contains Mi.

Input

In the first line n is given. In the second line, n integers are given. In the third line q is given. Then, in the fourth line, q integers (Mi) are given.

Output

For each question Mi, print yes or no.

Constraints

n ≤ 20

 q ≤ 200 

1 ≤ elements in A ≤ 2000

1 ≤ Mi ≤ 2000

Sample Input 1

5
1 5 7 10 21
8
2 4 17 8 22 21 100 35

Sample Output 1

no
no
yes
yes
yes
yes
no
no

Notes

You can solve this problem by a Burte Force approach. Suppose solve(p, t) is a function which checkes whether you can make t by selecting elements after p-th element (inclusive). Then you can recursively call the following functions:

solve(0, M) 

solve(1, M-{sum created from elements before 1st element}) 

solve(2, M-{sum created from elements before 2nd element}) 

...

The recursive function has two choices: you selected p-th element and not. So, you can check solve(p+1, t-A[p]) and solve(p+1, t) in solve(p, t) to check the all combinations.

For example, the following figure shows that 8 can be made by A[0] + A[2].

Template in C
-->



Sample input:
5
1 5 7 10 21
8
2 4 17 8 22 21 100 35


Sample output:
no
no
yes
yes
yes
yes
no
no

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))

def solve (i, m):
    if m == 0:
        return True
    elif i >= n:
        return False
    res = solve(i+1, m) or solve(i+1, m-A[i])
    return res

for m in M:
    if m < min(A) or m>sum(A):
        print('no')
    else:
        if solve(0, m):
            print('yes')
        else:
            print('no')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

# というわけで一旦全パターンを計算してから評価する事にする

n = int(input())
A = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
result = []
depth = -1
sum = 0


def main():
    calc(depth, sum)
    for i in m:
        if i in result:
            print('yes')
        else:
            print('no')


def calc(depth, sum):
    if depth >= n - 1:
        result.append(sum)
        return

    calc(depth + 1, sum + A[depth])
    calc(depth + 1, sum)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve(i, m):
	if m == 0:
		return True
	elif i >= n or m < 0:
		return False
	else:
		return solve(i + 1, m) or solve(i + 1, m - A[i])


if __name__ == "__main__":
	n = int(input())
	A = [int(x) for x in input().split()]
	q = int(input())
	M = [int(x) for x in input().split()]
	minA = min(A)
	sumA = sum(A)
	for m in M:
		if m < minA or m > sumA:
			print('no')
		elif solve(0, m):
			print('yes')
		else:
			print('no')

Submission status: Accepted

Solution code:
from itertools import combinations
n=int(input())
A=list(map(int,input().split()))
C=[]
for i in range(1,n+1):
  C+=list(map(sum,combinations(A,i)))
q=int(input())
M=list(map(int,input().split()))
for m in M:
  print("yes" if m in C else "no")

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_A
# 典型的なナップサック問題。動的計画法を使いたくなるが制約条件がゆるいので全探索でも十分間に合う。
# bit全探索を実装したくなるがここでは練習のために再帰関数で解く。

n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))

# i番目を以降の要素でmを作れるかどうかの関数solve(i,m)を再帰的に実装
# 例えば1 5 7 10 21が与えられたときsolve(4,21),solve(4,0)はTrue,solve(4,3)はFalseとすぐわかる
# ではsolve(3, x)はどうだろう。solve(3,31)はsolve(4,31)(つまり3番目の要素を選択しない)がTrueならTrueとなる。
# もしくはsolve(4,21)がTrueならsolve(3,31)もTrue (3番目の要素を選択したら実行可能).
# ここでは更に何も取らない選択も用意しておくと便利だろう。つまりsolve(5,0)ならばTrue
# つまり一般化すると、solve(i,m)はsolve(i+1,m)かsolve(i+1,m-A[i])がTrueならTrueでそれ以外はFalse
# またsolve(hoge,0)は必ず実行可能（再帰の終了条件）
# 以上を用いてDPテーブルを作成できちゃうが今回はあえて再帰的に実装する


from functools import lru_cache

# pythonだとTLEしてしまうためメモ化します


@lru_cache(maxsize=2**12)
def solve(i, m):
    # 終了条件 #dpテーブルの初期条件に相当
    if m == 0:
        return True
        # 数字をAでやりくりした結果切りよく0になるということは、その数字を実現可能だということ
        # 最大でi=len(A)、このときmは必ず0となるので無限ループは回避できる
    if i == n:
        # i==len(A)のときに前のifでm==0となればいいのだが、そうでないならば数字をAやりくりしても実現不可なのでFalseを返す
        return False

    return solve(i+1, m) or solve(i+1, m-A[i])


for m in M:
    if solve(0, m):
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
n = int(input())
NUM_LIST = list(map(int, input().split()))

k = int(input())
keys = list(map(int, input().split()))

check = [False]*2001
def recursive(index, sum_value):
    if index == n:
        check[sum_value] = True
        return
    
    recursive(index+1, sum_value)
    
    if sum_value + NUM_LIST[index] <= 2000:
        recursive(index+1, sum_value+NUM_LIST[index])

recursive(0, 0)

for key in keys:
    if check[key]:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
import bisect

n=int(input())
A=list(map(int,input().split()))
q=int(input())
m=list(map(int,input().split()))

l=[]
for k in range(2**n):
    a=0
    for i in range(n):
        if (k>>i)&1==1:
            a+=A[i]
    l.append(a)
l.sort()

for mi in m:
    if bisect.bisect_left(l,mi)<bisect.bisect_right(l,mi):
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
 
n = int(input())
A = list(map(int, input().split()))

q = int(input())
M = list(map(int, input().split()))


def solve(index, value):
  if value == 0:
    return True
  if index > n - 1:
    return False
  return solve(index + 1, value) or solve(index + 1, value - A[index])

for m in M:
  if sum(A) < m:
    print("no")
  else:
    print("yes" if solve(0, m) else "no")

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    q = int(input())
    m = [int(x) for x in input().split()]
    ans = ["no"] * q
    for j in range(2 ** n):
        total = 0
        for k in range(n):
            if (j >> k) & 1:
                total += a[k]
        if total in m:
            for i, v in enumerate(m):
                if v == total:
                    ans[i] = "yes"

    print("\n".join(map(str, ans)))


main()

Submission status: Accepted

Solution code:
import itertools

def hash_map(l, n):
  l_pairs = []
  for i in range(2, n+1):
    l_pairs += list(itertools.combinations(l, i))

  mapping = l
  for pair in l_pairs:
    mapping.append(sum(pair))

  return mapping

n = int(input())
list_a = list(map(int, input().split()))
q = int(input())
list_m = list(map(int, input().split()))

mapping = hash_map(list_a, n)

for m in list_m:
  if m in mapping: 
    print('yes')
  else:
    print('no')

Submission status: Accepted

Solution code:
n = int(input())
A = [int(i) for i in input().split()]

q = int(input())
m = [int(i) for i in input().split()]

def dfs(idx, s, target):
    if s + sum(A[idx:]) < target:
        return 0
    if s == target:
        return 1
    if s > target or idx == n:
        return 0

    return dfs(idx+1, s, target) or dfs(idx+1, s + A[idx], target)

for target in m:
    ans = 'yes' if dfs(0, 0, target) else 'no'
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))

dict_m = {}

def dfs(idx, sum_v):
    if idx == n:
        dict_m[sum_v] = True
        return
    
    dfs(idx+1, sum_v)
    dfs(idx+1, sum_v+A[idx])

dfs(0, 0)
for m in M:
    if m in dict_m:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
def solve(i, m):
    if m == 0:
        return True
    elif m < 0:
        return False
    if i >= n:
        return False
    return solve(i + 1, m) or solve(i + 1, m - A[i])
    
if __name__ == '__main__':
    yes = set()
    no = set()
    n = int(input())
    A = list(map(int,input().split()))
    q = int(input())
    m = list(map(int,input().split()))
    s = sum(A)
    for i in range(q):
        if s < m[i]:
            print('no')
            no.add(m[i])
        elif m[i] in yes:
            print('yes')
        elif m[i] in no:
            print('no')
        elif solve(0, m[i]):
            print('yes')
            yes.add(m[i])
        else :
            print('no')
            no.add(m[i])

Submission status: Accepted

Solution code:
num = int(input())
array = [int(x) for x in input().split()]
m = int(input())
l = [ int(x) for x in input().split()]


s = {0}
for i in array:
    s |= { x + i for x in s }


for q in l :
    if q in s:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
def solve(dp, a, i, m):
  if m in dp[i]:
    return dp[i][m]

  if m == 0:
    dp[i][m] = True
  elif i >= len(a):
    dp[i][m] = False
  elif solve(dp, a, i+1, m):
    dp[i][m] = True
  elif solve(dp, a, i+1, m-a[i]):
    dp[i][m] = True
  else:
    dp[i][m] = False

  return dp[i][m]

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
M = list(map(int, input().split()))

dp = {}
for i in range(N+1):
  dp[i] = {}

for m in M:
  if solve(dp, A, 0, m):
    print('yes')
  else:
    print('no')

Submission status: Accepted

Solution code:
n = int(input())
A = [int(i) for i in input().split()]
q = int(input())
m = [int(i) for i in input().split()]
memo = []

for i in range(2**n):
  tmp = 0
  for j in range(n):
    if i>>j & 1:
      tmp += A[j]
  memo.append(tmp)
for i in range(q):
  if m[i] in memo:
    print("yes")
  else:
    print("no")

Submission status: Accepted

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))

lst = [0]

for i in range(len(a)):
    tmp = []
    for sm in lst:
        tmp.append(sm+a[i])
    lst += tmp

lst.sort()

ans = ["no"]*q
for i in range(q):
    left = bisect.bisect_left(lst,m[i])
    if left != len(lst):
        if lst[left] == m[i]:
            ans[i] ="yes"
for i in range(q):
    print(ans[i])

Submission status: Accepted

Solution code:

n=int(input())
S=list(map(int,input().split()))
q=int(input())
T=list(map(int,input().split()))

list=[]
for i in range(pow(2,n)):
    num=0
    for j in range(n):
        if((i>>j) & 1):
            num+=S[j]
    list.append(num)

S=sorted(list)
n=len(S)
#print(S)

def isOK(index,key):
    if S[index]>=key:
        return True
    else:
        return False


def binary_search(key):
    left=0
    right=n-1

    while(right-left>1):
        mid = int(left+(right-left)/2)
        if isOK(mid,key):
            right = mid
        else:
            left = mid

    return right

ans=0
for x in T:
    #print("x",x)
    index=binary_search(x)
    if x==S[index]:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
import sys

def check(i,sum,Mi_max,n,A,cA):

	if i == n:
		if sum-1 < Mi_max:
#			print(f"{i},{sum}")
			cA[sum-1] = 1
		return True

	if i != 0 and sum > 0 and sum-1 < Mi_max:
#		print(f"{i},{sum}")
		cA[sum-1] = 1

	res = check(i+1,sum+A[i],Mi_max,n,A,cA) or check(i+1,sum,Mi_max,n,A,cA)

def test():

#	with open("in.txt",mode='r') as f:
#		n = int(f.readline())
#		A = list(map(int,f.readline().split()))
#		q = int(f.readline())
#		M = list(map(int,f.readline().split()))

	n = int(sys.stdin.readline())
	A = list(map(int,sys.stdin.readline().split()))
	q = int(sys.stdin.readline())
	M = list(map(int,sys.stdin.readline().split()))

	Mi_max = 0

	for i in M:
		if Mi_max < i:
			Mi_max = i
#	print(Mi_max)

	check_array = [0] * Mi_max

	check(0,0,Mi_max,n,A,check_array)

#	for i in range(len(check_array)):
#		print(f"{i+1}:{check_array[i]}")

	for i in M:
		if check_array[i-1] == 1:
			print("yes")
		else:
			print("no")

if __name__ == "__main__":
	test()

Submission status: Accepted

Solution code:
import itertools

n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))

"""Aの組み合わせ毎の合計を集合Bに追加"""
B = {sum(v) for i in range(n) for v in itertools.combinations(A, i+1)}

for m in M:
    print('yes' if m in B else 'no')

Submission status: Accepted

Solution code:
def setup_combination_map(idx, seq, sum):
    if idx >= len(seq):
        ans_map[sum] = True
        return

    setup_combination_map(idx+1, seq, sum)
    setup_combination_map(idx + 1, seq, sum+seq[idx])
    return

n_num = int(input())
n_seq = [int(s) for s in input().split()]
q_num = int(input())
q_seq = [int(s) for s in input().split()]
ans_map = [False] * 2048
setup_combination_map(0, n_seq, 0)

for q in q_seq:
    if ans_map[q]:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int, input().split()))
sum_s = sum(s)

q = int(input())
m = list(map(int, input().split()))

def slove(i, m):
    if m == 0:
        return True
    if i >= n or m < 0 or m > sum_s:
        return False
        
    return slove(i + 1, m) or slove(i + 1, m - s[i])

answer_cache = dict()
for j in m:
    if j in answer_cache:
        print(answer_cache[j])
        continue

    word = "yes" if slove(0, j) else "no"
    print(word)
    answer_cache[j] = word

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline()[:-1]
n=int(input())
A=list(map(int,input().split()))
q=int(input())
M=list(map(int,input().split()))

dp=[[0]*2001 for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
	for j in range(2001):
		# print(i-1)
		if 0<=j-A[i-1]<=2000:
			dp[i][j]=dp[i-1][j-A[i-1]] or dp[i-1][j]
		else:
			dp[i][j]=dp[i-1][j]

for m in M:
		print('yes' if dp[n][m] else 'no')
# for i in dp:
# 	print(i)
# print(dp[0][0])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def solve(A, i, n, m):
    if m == 0:
        return True
    if i >= n:
        return False
    return solve(A, i + 1, n, m) or solve(A, i + 1, n, m - A[i])

def main():
    n = int(input())
    A = list(map(int, input().split()))

    _ = int(input())
    m_list = list(map(int, input().split()))
    sum_list = sum(A)

    for m in m_list:
        if sum_list < m:
            print("no")
        elif solve(A, 0, n, m):
            print("yes")
        else:
            print("no")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
A = [int(x) for x in input().split()]
sumA = 0
for a in A:
    sumA += a
q = int(input())
M = [int(x) for x in input().split()]

def solve(i, m):
    if m == 0:
        return True
    elif i >= n or m < 0 or m > sumA: #A[i] < 0 があり得るならm < 0はダメ
        return False
    return solve(i + 1, m) or solve(i + 1, m - A[i])

for i in range(q):
    if solve(0, M[i]) == True:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
dp = [[None] * 2000 for i in range(n + 1)]


def solve(i, m):
    if dp[i][m] is not None:
        return dp[i][m]
    if m == 0:
        dp[i][m] = True
    elif i >= n:
        dp[i][m] = False
    elif solve(i + 1, m) or solve(i + 1, m - A[i]):
        dp[i][m] = True
    else:
        dp[i][m] = False
    return dp[i][m]


q = int(input())
M = list(map(int, input().split()))

for i in range(q):
    if solve(0, M[i]):
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
n = int(input())
aaa = list(map(int, input().split()))
q = int(input())
mmm = list(map(int, input().split()))
suma = sum(aaa)
def solve(i,m):
  global n,aaa,suma
  if m<0 or m>suma:
    return False
  if m==0:
    return True
  if i >= n:
    return False
  return solve(i+1,m) or solve(i+1,m-aaa[i])
mina = min(aaa)
for m in mmm:
  if m < mina or m>suma:
    print("no")
  else:
    if solve(0,m):
      print("yes")
    else:
      print("no")

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))

def check(i, s, m):
    if s == m:
        return True
    if s > m or i == n:
        return False
    if s + sum(A[i:]) < m:
        return False    
    return check(i+1, s, m) or check(i+1, s+A[i], m)

for m in M:
    if check(0, 0, m):
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
n = int(input())
A = [int(i) for i in input().split()]
 
q = int(input())
m = [int(i) for i in input().split()]
 
def dfs(idx, s, target):
    if s == target:
        return 1
     
    if s > target or idx == n:
        return 0
    if s + sum(A[idx:]) < target:
        return 0
 
    return dfs(idx+1, s, target) or dfs(idx+1, s + A[idx], target)
 
for target in m:
    ans = 'yes' if dfs(0, 0, target) else 'no'
    print(ans)

Submission status: Accepted

Solution code:
def solve(i, s):
    global A
    global M
 
    if i < len(A):
        M.add(s + A[i])
        solve(i + 1, s + A[i])
        solve(i + 1, s)
 
 
n = int(input())
A = [int(x) for x in input().split()]
M = set()
 
solve(0, 0)
 
q = int(input())
 
for m in [int(x) for x in input().split()]:
    if m in M:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:

def main():
    n = int(input())
    A = list(map(int, input().split(' ')))
    q = int(input())
    ms = list(map(int, input().split(' ')))
    results = _enumerate(A)

    for m in ms:
        if m in results:
            print('yes')
        else:
            print('no')



def _enumerate(lst):
    result = [0]
    for e in lst:
        n = len(result)
        for i in range(n):
            result.append(result[i]+e)
    return list(set(result))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
分割統治法
総当たり

長さnの数列Aと整数mに対して、Aの中のいくつかの要素を足し合わせてmが作れるかどうか
n < 20
2^20 < 10^7なので、全部やる
"""

n = int(input())
As = list(map(int, input().split()))
q = int(input())
ms = list(map(int, input().split()))

import sys
sys.setrecursionlimit(100000)
# たかだか2000個なので、sum可能なデータの結果を全部持っておくと、再計算の必要がない
check_values = [False]*2016
flg = False
def dfs(i,sum):
    global flg
    if sum > 2000:
        return 0
    if i+1 == n:
        check_values[sum] = True
        return 0 
    for loop in [0,1]:
        dfs(i+1,sum+As[i+1]*loop)

dfs(-1,0)
for m in ms:
    flg = check_values[m]
    if flg:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
n=int(input())
a=[int(i) for i in input().split()]
s=sum(a)

def rec(i,num):
    if num==0:
        return True
    if i>=n or num<0 or num>s:
        return False
    res=rec(i+1,num) or rec(i+1,num-a[i])
    return res

q=int(input())
m=[int(i) for i in input().split()]
for i in m:
    print("yes" if rec(0,i) else "no")

Submission status: Accepted

Solution code:
from typing import List


def solve(index: int, elements: List[int], target_value: int) -> bool:
    if target_value < 0:
        return False
    elif 0 == target_value:
        return True
    elif len(elements) == index:
        return False

    return solve(index + 1, elements, target_value - elements[index]) or solve(index + 1, elements, target_value)


if __name__ == "__main__":
    _ = int(input())
    elements = list(map(lambda x: int(x), input().split()))
    min_elem = min(elements)
    sum_elem = sum(elements)
    _ = int(input())
    m_list = list(map(lambda x: int(x), input().split()))

    for m in m_list:
        if m < min_elem or sum_elem < m:
            print("no")
        else:
            if solve(0, elements, m):
                print("yes")
            else:
                print("no")

Submission status: Accepted

Solution code:

if __name__ == '__main__':
    n = int(input())
    A = list(map(int, input().split()))
    S = set()

    def solve(i, x):

        if i < n:
            S.add(x + A[i])
            solve(i + 1, x + A[i])
            solve(i + 1, x)

    solve(0, 0)

    q = int(input())
    for i in input().split():
        if int(i) in S:
            print('yes')
        else:
            print('no')

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
m = [int(i) for i in input().split()]

a.sort()
for ans in m:
	dp = [[0 for i in range(ans+1)] for k in range(len(a)+1)]
	dp[0][0] = 1
	for i in range(len(a)):
		for k in range(ans+1):
			if a[i] <= k:
				dp[i+1][k] = dp[i][k-a[i]] or dp[i][k]
			else:
				dp[i+1][k] = dp[i][k]
	if dp[len(a)][ans]:
		print("yes")
	else:
		print("no")

Submission status: Accepted

Solution code:

n = 0
A = []
q = 0
M = []
D = [[-1 for j in range(2000 + 1)] for i in range(20 + 1)]


def solve(i, m):
    # can m be formed in A[i:]?
    global n, A
    if m == 0:
        return 1
    if m < 0:
        return 0
    # m > 0 here
    if i == n:
        return 0
    # m > 0 and i < n here
    if D[i][m] != -1:
        return D[i][m]

    D[i][m] = solve(i + 1, m) or solve(i + 1, m - A[i])
    return D[i][m]


if __name__ == '__main__':
    n = int(raw_input())
    A = map(int, raw_input().split())
    q = int(raw_input())
    M = map(int, raw_input().split())
    for m in M:
        if solve(0, m):
            print "yes"
        else:
            print "no"

Submission status: Accepted

Solution code:
from enum import Enum
from queue import Queue
import collections

import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

global n,A

n = int(input())
A = list(map(int,input().split()))
q = int(input())
m = list(map(int,input().split()))
s=set({})

def solve(i,m):
    if i == n:
        s.add(m)
        return
    solve(i+1,m+A[i])
    solve(i+1,m)

solve(0,0)
for i in m:
    if i in s:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
def inner_prod(vec_a, vec_b):
    from functools import reduce

    return reduce(lambda acc, tpl: acc + tpl[0] * tpl[1], zip(vec_a, vec_b), 0)


def generate_combinations(size, trunk, A=[]):
    if len(A) == size:
        return
    trunk.append(A + [0])
    trunk.append(A + [1])
    generate_combinations(size, trunk, A + [0])
    generate_combinations(size, trunk, A + [1])


n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))

comb = []
generate_combinations(n, comb)
for i in range(len(comb)):
    comb[i] += [0] * (n - len(comb[i]))

trunk = set()
for c in comb:
    trunk.add(inner_prod(A, c))

for m in M:
    print("yes" if m in trunk else "no")

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))

def solve(idx, current, target):
        # print("\n# i: " + str(i))
        # print("# current: " + str(current))
        # print("# target: " + str(target))
        # print("# array: " + str(array))
    if current > target:
        return False
    elif len(A) == idx:
        return False
    elif current + sum(A[idx:])	< target:
        return False
    elif current == target:
        return True
    elif current + A[idx] == target:
        return True
    else:
        return solve(idx + 1, current + A[idx], target) or solve(idx + 1, current, target)

for i in range(q):
    if solve(0, 0, M[i]):
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int, input().split()))
q = int(input())
questions = list(map(int, input().split()))

answers = set()
for i in range(1, 2 ** n):
    bin_i = "{:020b}".format(i)[::-1]

    answer = sum(arr[x] for x in range(n) if bin_i[x] == "1")
    answers.add(answer)

for question in questions:
    print("yes" if question in answers else "no")

Submission status: Accepted

Solution code:
n=int(input())
da=list(map(int,input().split()))
ans=[0 for i in range(2**n)]
jud=[False for i in range(n)]

def cal(i):
    k=i
    su=0
    for j in range(n):
        if k%2==1:
            su+=da[j]
        k//=2
    ans[i]=su

for i in range(2**n):
    cal(i)
kop=set(ans)
m=int(input())
qu=list(map(int,input().split()))
for i in qu:
    if len({i}&kop):
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
def solve(m, a, n, i):
    if m == 0:
        return True
    if i >= n:
        return False
    return solve(m, a, n, i+1) or solve(m-a[i], a, n, i+1)


def main():
    n = int(input())
    a = list(map(int, input().split()))
    q = int(input())
    M = list(map(int, input().split()))
    for m in M:
        if m < min(a) or m > sum(a):
            print("no")
        elif solve(m, a, n, 0):
            print("yes")
        else:
            print("no")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def is_solved(i, m):
    if   m == 0:
        return True
    elif m < 0:
        return False

    if i >= len(A):
        return False

    flag_solved = is_solved(i + 1, m) or is_solved(i + 1, m - A[i])

    return flag_solved


n = input()
A = list(map(int, input().split()))
q = input()
M = list(map(int, input().split()))

sum_A = sum(A)


for m in M:
    if m > sum_A:
        print("no")
        continue
    
    if is_solved(0, m):
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(lambda x:int(x),input().split()))
q=int(input())
m=list(map(lambda x:int(x),input().split()))
sumlist=[]
bin=[0]*n

def suc(bin):
    i=-1
    while bin[i]==1:
        bin[i]=0
        i=i-1
    bin[i]=1
    return(bin)

for i in range(2**n-1):
    tmpsum=0
    for j in range(n):
        if bin[j]==1:
            tmpsum+=a[j]
    sumlist.append(tmpsum)
    bin=suc(bin)

for i in m:
    flag=True
    for j in sumlist:
        if i==j:
            print("yes")
            flag=False
            break
    if flag:
        print("no")

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))

def foo(target, index):
    if target == 0:
        return True

    if index >= n:
        return False

    res = foo(target, index + 1) or foo(target - A[index], index + 1)
    return res

sum = sum(A)

for mi in m:
    if (mi > sum):
        print('no')
        continue

    ret = foo(mi, 0)
    if ret:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
q = int(input())
m = list(map(int,input().split()))

def dp(sums,depth,data):
	if sums < 0 or sums > sum(data):
		return False
	if sums == 0:
		return True
	if depth >= len(data):
		return False

	return dp(sums,depth+1,data) or dp(sums-data[depth],depth+1,data)

for i in m:
	if i < min(A) or i > sum(A):
		print("no")
	else:
		print("yes" if dp(i,0,A) else "no")

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
Q = int(input())
M = [int(i) for i in input().split()]
dp = [[-1] * (max(M) + 1) for _ in range(N + 1)]

def rec(i, m):
    if m == 0:
        return True
    if i >= N or m < 0:
        return False
    if dp[i][m] != -1:
        return dp[i][m]
    res = rec(i + 1, m) or rec(i + 1, m - A[i])
    dp[i][m] = res
    return res


for m in M:
    print('yes' if rec(0, m) else 'no')

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    import copy

    n = int(input())

    aa = list(map(int, input().split()))

    q = int(input())

    ans = set()

    for a in aa:
        for element in copy.deepcopy(ans):
            ans.add(element+a)
        ans.add(a)

    for m in map(int, input().split()):
        if m in ans:
            print('yes')
        else:
            print('no')

Submission status: Accepted

Solution code:
from functools import lru_cache

n = int(input())
A = [int(i) for i in input().split()]

@lru_cache(maxsize=1000000)
def solveBruteForce(p, t):
    if t == 0:
        return True
    elif t < 0:
        return False
    elif p == n:
        return False
    elif solveBruteForce(p+1, t-A[p]):
        return True
    elif solveBruteForce(p+1, t):
        return True
    else:
        return False

M = int(input())
q = [int(i) for i in input().split()]
for mi in range(M):
    if solveBruteForce(0, q[mi]):
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
from sys import stdin

def ExhaustiveSearch(A :list,n : int,M :list,ANS :list):
	A = [0 for _ in range(n)]
	rec(0,A,n,M,ANS)

def rec(i : int, A : list, n : int,M :list,ANS : list):

	if i == n:
		sm = 0
		for j,k in enumerate(A):
			if k == 1:
				sm += int(M[j])
		ANS.append(sm)
		return

	A[i] = 0
	rec(i+1,A,n,M,ANS)

	A[i] = 1
	rec(i+1,A,n,M,ANS)


if __name__ == '__main__':

	A = []
	ANS = []

	n = int(input())
	inlist = stdin.readline().strip().split()

	input()
	outlist = list(map(int,stdin.readline().strip().split()))

	ExhaustiveSearch(A,len(inlist),inlist,ANS)
	ANS.sort()
	for i in outlist:
		if i in ANS:
			print("yes")
		else:
			print("no")

Submission status: Accepted

Solution code:
n = int(input())
a = [int(num) for num in input().split(" ")]
q = int(input())
m = [int(num) for num in input().split(" ")]

def build_combinations(n, a):
    result = []
    decide_next(n, a, 0, 0, result)
    return result

def decide_next(n, a, i, sum, result):
    if i == n:
        result.append(sum)
        return
    # Choosing a[i]
    decide_next(n, a, i+1, sum + a[i], result)
    # Not choosing a[i]
    decide_next(n, a, i+1, sum, result)

combinations = build_combinations(n, a)

for i in m:
    flag = "no"
    for j in combinations:
        if i == j:
            flag = "yes"
            break
    print(flag)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = list(map(int, input().split()))
li = []
for i in range(2**n):
  total = 0
  for j in range(n):
    if ((i>>j)&1):
      total += a[j]
  li.append(total)

for p in b:
  if p in li:
    print('yes')
  else:
    print('no')

Submission status: Accepted

Solution code:
def solve():
    from itertools import product
    input()
    A = tuple(map(lambda x: (0, int(x)), input().split()))
    result = [0]*(2000*20+1)
    for a in product(*A):
        result[sum(a)] = 1

    input()
    print(*("yes" if result[q] else "no" for q in map(int, input().split())), sep="\n")


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys


def solve(i, m):
    if dp[i][m] > -1:
        return dp[i][m]
    
    if m == 0:
        return 1
    elif i >= n:
        dp[i][m] = 0
    elif solve(i+1, m):
        dp[i][m] = 1
    elif solve(i+1, m-a_list[i]):
        dp[i][m] = 1
    else:
        dp[i][m] = 0
    
    return dp[i][m]


input = sys.stdin.readline
n = int(input())
a_list = list(map(int, input().split()))
q = int(input())
m_list = list(map(int, input().split()))

dp = [[-1]*2000 for i in range(n+1)]

for m in m_list:
    if solve(0, m):
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))


def memoize(f):  # メモ化関数
    table = [{} for _ in range(n+1)]

    def func(cur, m):
        if m not in table[cur]:
            table[cur][m] = f(cur, m)
        return table[cur][m]
    return func


# メモ再帰で書く
@memoize
def dfs(cur, m):
    if m == 0:
        return True
    if cur >= n:
        return False
    res = dfs(cur+1, m) | dfs(cur+1, m-A[cur])
    return res


for num in m:
    if dfs(0, num):
        print('yes')
    else:
        print('no')