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:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
lst = set()
for i in a:
    templ = list(lst)
    for j in templ:
        lst.add(i+j)
    lst.add(i)
for i in m:
    if i in lst:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
from collections import defaultdict

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

D = defaultdict(bool)

for i in range(2**n):
    tmp = 0
    for j in range(n):
        if i>>j & 1:
            tmp += A[j]
    D[tmp] = True

q = int(input())

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

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

Submission status: Accepted

Solution code:
def solve(i, m, A, n):

    if m == 0:
        return True

    elif i >= n:
        return False

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

def main():
    n = int(input())
    A = [int(a) for a in input().split()]
    q = int(input())
    M = [int(a) for a in input().split()]

    sum_A = sum(A)

    for m in M:

        if m > sum_A:
            print("no")
            continue

        if solve(0, m, A, n):
            print("yes")
        else:
            print("no")

main()

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()))
ans = []
mem = [0] * 2**n
for i in range(2 ** n):
    total = 0
    for j in range(n):
        if i >> j & 1:
            total += A[j]
            # if total > m:
            #     break
    mem[i] = total
    # if total == m:
    #     print('yes')
    #     break
# else:
#     print('no')
for m in M:
    if m > sum(A):
        print('no')
        continue
    if mem.count(m):
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
#アルゴリズム
def solve(i, s):
    global n_list
    global sum_list
    
    if i < len(n_list):
        sum_list.add(s + n_list[i])
        solve(i + 1, s + n_list[i])
        solve(i + 1, s)

#初期値
n = int(input())
n_list = list(map(int, input().split()))
sum_list = set()

#合計値の計算
solve(0, 0)

#判定値
q = int(input())
q_list = list(map(int, input().split()))

#結果表示
for i in range(q):
    if q_list[i] in sum_list:
        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()))

ans = [False for i in range(2001)]
ans[0] = True

for i in range(N):
    for j in range(2000, -1, -1):
        if ans[j]:
            if j+A[i] <= 2000:
                ans[j+A[i]] = True
for i in range(Q):
    if ans[M[i]]:
        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()))

from functools import lru_cache
# メモ化
@lru_cache(maxsize=2**12)

def solve(i, m):
    if (m == 0):
        return True
    elif (i == N):
        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())
A = [int(i) for i in input().split()]
q = int(input())
M = [int(i) for i in input().split()]
bit = 1
for a in A:
    bit |= bit<<a
for m in M:
    if bit & 1<<m:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
def func(idx,s,p):
    global a
    if s == p:
        return True
    if s > p or idx == n:
        return False
    if s + sum(a[idx:]) < p:
        return False
    return func(idx+1,s,p) or func(idx+1,s+a[idx],p)


n = int(input())
a = [int(s) for s in input().split()]
m = int(input())
b = [int(t) for t in input().split()]
a.sort()

for i in b:
    if func(0,0,i):
        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()))

ans=[0]
for i in range(n):
    ans_bkup=ans.copy()
    ans=list(map(lambda x: x+a[i],ans))
#    print(ans,ans_bkup)
    ans.extend(ans_bkup)
    ans=list(set(ans))

for i in range(q):
    if(m[i] in ans):
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
import itertools


n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
m = [int(i) for i in input().split()]
total = set()

for bits in itertools.product([0, 1], repeat=n):
    total.add(sum([i * j for (i, j) in zip(a, bits)]))

ans = ["yes" if x in total else "no" for x in m]
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
n=int(input())
A=[]
A=input().split()
A=[int(u) for u in A]
A.sort()
q=int(input())
S=[]
S=input().split()
S=[int(u) for u in S]
coun=0
for i in range(0,n):
    coun=coun+A[i]
K=[[0 for j in range(coun+1)] for i in range(n)]
T=[]
for i in range(0,n):
    K[i][0]=0
for j in range(0,coun+1):
    T.append(0)
for j in range(1,coun+1):
    if A[0]==j:
        K[0][j]=1
        T[j]=1
    else:
        K[0][j]=0
koe=A[0]
for i in range(1,n):
    koe=koe+A[i]
    for j in range(1,coun+1):
        j=coun+1-j
        u=j-A[i]
        if koe<j:
            K[i][j]=0
        elif koe==j:
            K[i][j]=1
            T[koe]=1
        elif A[i]==j:
            K[i][j]=1
            T[j]=1
        elif T[u]==1 and j<=koe and u>=0:
            T[j]=1
            K[i][j]=1
        else:
            K[i][j]=0
s=len(S)
for i in range(0,s):
    o=S[i]
    if o>coun:
        print("no")
    elif T[o]==1 and o<=coun:
        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()))

MAX = 2000
check = [False]*(MAX+1)

def ExhaustiveSearch(index, tmp_sum):
    global n

    if index == n:
        check[tmp_sum] = True #ハッシュ
        return
    
    ExhaustiveSearch(index+1, tmp_sum) #足さないという選択
    if tmp_sum+a[index]<2000:
        ExhaustiveSearch(index+1, tmp_sum+a[index])

ExhaustiveSearch(0, 0)
for i in range(q):
    if check[m[i]]:
        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()))
dp = [[None for i in range(2001)] for i in range(21)]

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

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

Submission status: Accepted

Solution code:
import itertools

n = int(input())
A = tuple(map(int, input().split()))
q = int(input())
B = tuple(map(int, input().split()))

memo = set()
for i in range(1, n + 1):
    for nums in itertools.combinations(A, i):
        memo.add(sum(nums))

for m in B:
    print('yes' if m in memo 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()]

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

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

Submission status: Accepted

Solution code:
input()
X = [int(x) for x in input().split()]
input()
Y = [int(x) for x in input().split()]

flag = [False]* 2000
for j in range(1 << len(X)):
    n = 0
    for i in range(len(X)):
        if 1 & (j >> i) == 1:
            n += X[i]
    flag[n] = True

for m in Y:
    print("yes" if flag[m] else "no")

Submission status: Accepted

Solution code:

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

n = int(input())
A = list(map(int, input().split())) 
p = int(input())
B = list(map(int, input().split())) 
C = {}
for num in B:
    if solve(0, num):
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
from itertools import combinations, chain
n = int(input())
A = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
S = list(map(sum, chain.from_iterable(combinations(A, r) for r in range(n))))
ans = map(lambda y: 'yes' if y else 'no', map(lambda x: x in S, m))
print('\n'.join(ans))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
m=int(input())
b=list(map(int,input().split()))
def two(x):
	s="0"*(n-len(bin(x))+2)
	return s+bin(x)[2:]
ans=set()
for i in range(2**n):
	p=0
	for j in range(n):
		if two(i)[j]=="1":
			p+=a[j]
	ans.add(p)
for i in range(m):
	if b[i] in ans:
		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()]

list.sort(A, reverse=True)

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

sum_A=sum(A)

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

Submission status: Accepted

Solution code:
def solve(i: int, A: list, meolist: list, m: int):
    if m == 0:
        return True
    elif m in meolist[i].keys():
        return meolist[i][m]
    
    if i >= len(A):
        meolist[i][m] = False
    elif solve(i + 1, A, meolist, m - A[i]) is True:
        meolist[i][m] = True
    elif solve(i + 1, A, meolist, m) is True:
        meolist[i][m] = True
    else:
        meolist[i][m] = False

    return meolist[i][m]

if __name__ == '__main__':
    n = int(input())
    A = [int(num) for num in input().split(' ')]
    m = int(input())
    mlist = [int(num) for num in input().split(' ')]

    # Memory array, store the num already cal
    meolist = [{} for i in range(n + 1)]

    for num in mlist:
        if solve(0, A, meolist, num):
            print('yes')
        else:
            print('no')

Submission status: Accepted

Solution code:
#coding: utf-8
n = int(input())
a = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
x = 2 ** n
L = list()
for i in range(x):
    temp = 0
    for j in range(n):
        if i & (1<<j):
            temp += a[j]
    L.append(temp)
for i in m:
    if i in L:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
a = int(input())
b = list(map(int, input().split()))
c = int(input())
d = list(map(int, input().split()))

nums = {0}

for i in range(a):
    p = nums.copy()
    for j in p:
        nums.add(b[i])
        nums.add(j+b[i])

for i in range(c):
    if d[i] in nums:
        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()))

poss = [0]
for i in A:
    tmp_poss = poss.copy()
    for j in poss:
        tmp_poss.append(i + j)
    poss = tmp_poss
poss.remove(0)

for i in m:
    if poss.count(i) >= 1:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
from bisect import bisect_right as br
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

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

    ss=set()
    ss.add(0)
    for a in aa:
        nss=set()
        for s in ss:
            nss.add(s)
            nss.add(s+a)
        ss=nss

    for q in qq:
        if q in ss:
            print("yes")
        else:
            print("no")

main()

Submission status: Accepted

Solution code:
#alds1_5_a


def exhaustive_search(m, i):
    global solved
    global A
#    if solved[m][i] is not None:
#        return solved[m][i]

    if A[i] == m:
        solved[m][i] = True
        return True

    if (i + 1) < len(A):
        return exhaustive_search(m - A[i], i+1) or exhaustive_search(m, i+1)
    else:
        solved[m][i] = False
        return False
    

if __name__ == "__main__":
    n = int(input())
    A = sorted(map(int, input().split()))
    q = input()
    solved = [[None for i in range(n)] for j in range(2000)]

    for m in map(int, input().split()):
        if sum(A) < m:
            print('no')
        elif exhaustive_search(m, 0):
            print('yes')
        else:
            print('no')

Submission status: Accepted

Solution code:
#1-5-A
n=int(input())
a=list(map(int,input().split()) )
q=int(input())
m=list(map(int,input().split()) )

s=[0]
for i in a:
    s.extend([i+j for j in s])
for i in m:
    if i in s:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
def main():
	n = int(input())
	a = list(map(int,input().split()))
	q = int(input())
	m = list(map(int,input().split()))
	lst = set()
	for i in a:
		templ = list(lst)
		for j in templ:
			lst.add(i+j)
		lst.add(i)
	for i in m:
		if i in lst:
			print("yes")
		else:
			print("no")

main()

Submission status: Accepted

Solution code:
def exhaustive(i,A,m,n):
    if m==0:
        return True
    if i>=n:
        return False
    
    return exhaustive(i+1,A,m,n) or exhaustive(i+1,A,m-A[i],n)
    
    
def inputting():
    n=int(input())
    A=list(map(int,input().split()))
    q=int(input())
    M=list(map(int,input().split()))
    return n,A,q,M

def main():
    A=[]
    M=[]
    n,A,q,M=inputting()
    total = sum(A)
    for m in M:
        if total<m:
            print("no")
            continue
        bool=exhaustive(0,A,m,n)
        if bool==True:
            print("yes")
        else:
            print("no")

if __name__=='__main__':
    main()

Submission status: Accepted

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


n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))
for i in range(q):
    if sum(A) < M[i]:
        print("no")
    elif solve(0, M[i]):
        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()))

iter = [[]]
for i in range(n):
  temp = []
  for cand in iter:
    temp.append(cand + [0])
    temp.append(cand + [1])
  iter = temp

Ans = []
for cand in iter:
  ans = 0
  for i in range(n):
    ans += cand[i] * A[i]
  Ans.append(ans)

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

Submission status: Accepted

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

binary=[0 for i in range(n)]
A_ls=[]

while 0 in binary:
    s=0
    for i in range(n):s+=A[i]*binary[i]
    A_ls.append(s)
    idx = binary.index(0)
    binary[idx]=1
    for i in range(idx):binary[i]=0
        
for j in m:
    if j in A_ls:print('yes')
    else:print('no')

Submission status: Accepted

Solution code:
input()
X = [int(x) for x in input().split()]
input()
Y = [int(x) for x in input().split()]

flag = [False]*2000
for j in range(1 << len(X)):
    n = 0
    for i in range(len(X)):
        if 1 & (j >> i) == 1:
            n += X[i]
    flag[n] = True

for m in Y:
    print("yes" if flag[m] else "no")

Submission status: Accepted

Solution code:
#! python3
# exhaustiveSearch.py - 総当りの計算

import itertools

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

def generateCombo(A):
    combo_set = []
    for i in range(len(A)):
        combo_set.extend(list(itertools.combinations(A, i+1)))
    return combo_set

combo_set = generateCombo(A)

sum_list = []
for combo in combo_set:
    sum_num = sum(combo)
    sum_list.append(sum_num)

for num in m:
    if num in sum_list:
        print('yes')
    else :
        print('no')

Submission status: Accepted

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

memo = {}
def solve(A, index, currS):
    key = str(index)+' '+str(currS)
    global memo
    if key in memo:
        return memo[key]
    else:
        if currS == 0:
            memo[key] = True
            return True
        elif currS < 0 or index >= len(A):
            memo[key] = False
            return False
        else:
            result1 = solve(A, index+1, currS)
            result2 = solve(A, index+1, currS-A[index])
            memo[key] = result1 or result2
            return memo[key]
for q in Q:
    if solve(A, 0, q):
        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()))

sum_A = sum(A)

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

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

Submission status: Accepted

Solution code:
def power_set(item_lists):

    p_sets = [[]]

    for item in item_lists:
        tmp = []
        for element in p_sets:
            tmp.append(element + [item])
        p_sets.extend(tmp)

    return p_sets



if __name__ == "__main__":
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    m = list(map(int, input().split()))

    p_set = [sum(l) for l in power_set(A)]

    for m_i in m:

        if m_i in p_set:
            print("yes")
        else:
            print("no")

Submission status: Accepted

Solution code:
import copy

n = int(input())
A = [int(x) for x in input().split()]
q = int(input())
M = [int(x) for x in input().split()]

c = [0]
S = [0]

for a in A:
  S = copy.copy(c)
  for  s in S:
    c.append(s+a)

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

Submission status: Accepted

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


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

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



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

Submission status: Accepted

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

#n=5
#M=[1,5,7,10,21]
#q=8
#N=[17]

def solve(i,m):
#    print("m:",m)
    if m==0:
        return True
    if i>=n:
        return False
#    print(f"solve({i+1},{m}) or solve({i+1},{m-M[i]})")
    return solve(i+1,m) or solve(i+1,m-M[i])

for cur in N:
    if   cur > sum(M):
        print("no")
    else:
        print("yes" if solve(0,cur) 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 check(i,m):
    if m<0 or m>sum(A):
        return False
    elif m==0:
        return True
    elif i>=n:
        return False

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

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

Submission status: Accepted

Solution code:
import math
def search(a,m):
               dp=[[False for _ in range(m+1)] for _ in range(len(a)+1)]
               dp[0][0]=True
               for i in range(len(a)):
                       for j in range(m+1):
                               if a[i]<=j:
                                       dp[i+1][j]=dp[i][j-a[i]] or dp[i][j]
                               else:
                                       dp[i+1][j]=dp[i][j]
               return dp[len(a)][m]
n=int(input())
a=list(map(int,input().split()))
q=int(input())
m=list(map(int,input().split()))

for i in m:
        if search(a,i):
                print("yes")
        else:
                print("no")

Submission status: Accepted

Solution code:

n=int(input())
a=[int(x) for x in input().split()]
m=int(input())
s=[int(x) for x in input().split()]

def cal(a):
    x=0
    while True:
        a[x]+=1
        if a[x]==2:
            a[x]=0
            x+=1
        else:
            break
    return a


mk=[0]*(n+1)
sums=[]

while  True:

    mk=cal(mk)
    if mk[n]==1:
        break
    ist=0
    for i in range(n):
        if mk[i]==1:
            ist+=a[i]
    sums.append(ist)

yon=[]

for b in range(m):
    if s[b] in sums:
        yon.append(str("yes"))
    else:
        yon.append(str("no"))

for h in range(m):
    print(yon[h])

Submission status: Accepted

Solution code:
import itertools
def solve(A):
    x = []
    for i in range(len(A)):
        comb = list(itertools.combinations(A, i))
        for c in comb:
            x.append(sum(c))
    return x
n = int(input())
A = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
s = solve(A)
for i in m:
    if 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()]
sup = 2000*20
# dp[i][j]: i番目までの整数を用いてjを作れるかどうかTrue/False
dp = [[False for i in range(sup)] for j in range(n+1)]
for i in range(1,n+1):
    for j in range(sup):
        dp[i][a[i-1]-1] = True
        if j-a[i-1] >= 0:
            dp[i][j] = dp[i-1][j] or dp[i-1][j-a[i-1]]
        else:
            dp[i][j] = dp[i-1][j]
# print(dp[-1][:10])
for i in range(q):
    if dp[-1][m[i]-1]:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
def part_sum(a,A):
    N=len(a)
    dp=[[0 for i in range(A+1)] for j in range(N+1)]
    dp[0][0]=1

    for i in range(N):
        for j in range(A+1):
            if a[i]<=j: 
                dp[i+1][j]=dp[i][j-a[i]] or dp[i][j]
            else: 
                dp[i+1][j]=dp[i][j]
    return dp[N][A]


n=int(input())

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

q=int(input())

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

for i in range(q):
    if(part_sum(A,M[i])==1):
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    _ = int(input())
    m = [int(i) for i in input().split()]
    sum_set = set()
    for bit in range(1 << N):
        cur_sum = 0
        for i in range(N):
            if bit & (1 << i):
                cur_sum += A[i]
        sum_set.add(cur_sum)
    for mm in m:
        if mm in sum_set:
            print("yes")
        else:
            print("no")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


N = int(input())
table = list(map(int,input().split()))

MAX = 2000
check = [False]*(MAX+1)

def recursive(index,tmp_sum):
    global N

    if index == N:
        check[tmp_sum] = True
        return

    recursive(index+1,tmp_sum)
    if tmp_sum+table[index] <= MAX:
        recursive(index+1,tmp_sum+table[index])

recursive(0,0)

num_query = int(input())
for num in list(map(int,input().split())):
    if check[num]:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from copy import deepcopy
inf=float('inf')
def main():
    N = int(input())
    *A, = map(int,input().split())
    Q = int(input())
    *B, = map(int,input().split())

    bit_max = 1<<N
    S = set()
    for bit in range(bit_max):
        sum_ = 0
        for i in range(N):
            if(bit & (1<<i)):
                sum_ += A[i]
        S.add(sum_)
    

    """S = set([0])
    for a in A:
        for s in deepcopy(S):
            S.add(a+s)
    """
    for q in B:
        if q in S:
            print("yes")
        else:
            print("no")

    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def reboot(arr, index, count, q):
    if index >= len(arr):
        return False
    if count > q:
        return False
    if count + arr[index] == q:
        return True
    elif count + arr[index] > q:
        return reboot(arr, index + 1, count, q)
    return reboot(arr, index + 1, count + arr[index], q) or reboot(arr, index + 1, count, q)


if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split()))
    q = int(input())
    q_arr = list(map(int, input().split()))
    min_ele = arr[0]
    arr_sum = arr[0]
    for i in range(1, len(arr)):
        min_ele = min(min_ele, arr[i])
        arr_sum += arr[i]
    for ele in q_arr:
        if ele < min_ele or ele > arr_sum:
            print('no')
        else:
            if reboot(arr, 0, 0, ele):
                print('yes')
            else:
                print('no')

Submission status: Accepted

Solution code:
import itertools

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

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

l=list()

for i in range(n):
    for j in itertools.combinations(a,i):
        #print(sum(j))
        l.append(sum(j))

for i in b:
    for j in l:
        if i in l:
            print("yes")
            break
        else:
            print("no")
            break

Submission status: Accepted

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

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

sum=[0]
for i in range(n):
    for j in range(len(sum)):
        sum.append(A[i]+sum[j])

for i in range(m):
    if q[i] in sum:
        print("yes")
    else:
        print("no")

Submission status: Accepted

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


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

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

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()))
fin=False
"""
def solve(i,m):
    global n
    if m==0:
        print("yes")
        fin=True
        return True
    if i>=n:
        return False
    solve(i+1,m) 
    solve(i+1,(m-A[i]))
    #return res
for i in range(q):
    fin=False
    cnt=0
    #for i in range(n):
    solve(0,m[i])
    if fin ==True:
        cnt=cnt+1
    if fin==False and cnt==0:
        print("no")
    #fin=False
"""

fin=False
s=[]
for i in range(n):
    fin=False
    S=list(itertools.combinations(A,i))
    for k in range(len(S)):
        t=sum(S[k])
        s.append(t)
for i in m:
    if i in s:
        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(i,num):
    if num==0:
        return True
    if i>=n:
        return False
    res=solve(i+1,num) or solve(i+1,num-A[i])
    return res




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

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()]
t = [0]
for i in range(n):
    for j in range(len(t)):
        t.append(t[j]+a[i])
for i in range(q):
    if m[i] in t:
        print("yes")
    else:
        print("no")

Submission status: Accepted

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

a = set()
def bf(sum_, n):
    global a, A
    
    a.add(sum_)
    if n < 0: return
    
    bf(sum_+A[n], n-1)
    bf(sum_, n-1)

bf(0, n-1)
for b in B:
    if b in a:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
def second_problem():
    length = int(input())
    numbers_array: [int] = list(map(lambda n: int(n), input().split(' ')))

    questions_len = int(input())
    questions: [int] = list(map(lambda n: int(n), input().split(' ')))
    answers: [str] = ['no'] * questions_len

    for state in range(pow(2, length)):

        bit_arr = [(state >> x) & 1 for x in range(length)]
        state_val = sum([val * bit for val, bit in zip(numbers_array, bit_arr)])

        # Don't check numbers that we already have answers for
        for q_index in range(len(questions)):
            q = questions[q_index]
            if q == state_val:
                answers[q_index] = 'yes'
                # print(f'found solution for {q} at {bit_arr}')

    for ans in answers:
        print(ans)


second_problem()

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
q = int(input())
M = list(map(int,input().split()))
def add_check(i,m):
    if m == 0:
        return True
    if m < 0 or m > sum(A[i:n]):
        return False
    if i >= n:
        return False
    if add_check(i+1,m) or add_check(i+1,m-A[i]):
        return True
for i in range(q):
    if add_check(0,M[i]):
        print("yes")
    else:
        print("no")