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
sys.setrecursionlimit(100000)  ##再帰呼び出しの上限設定
 


n=int(input())
A=[int(x) for x in input().split()]
minA=min(A)  ##Aの最小値
sumA=sum(A)  ##Ａの総和


 
q=int(input())
M=[int(x) for x in input().split()]
 
 
def solve(i,m):
    global n
    global A
    global minA
    global 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-A[i])
     
     
for m in M:
    if m<minA or m>sumA: ##そもそもAで実現不可
        print('no')
    else:
        if solve(0,m):
            print('yes')
        else:
            print('no')

Submission status: Accepted

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

def solve(x,y):
    if x==n:
        S[y] = 1
    else:
        solve(x+1,y)
        if y+A[x] < 2001:
            solve(x+1,y+A[x])
            
S = [0 for i in range(2001)]

solve(0,0)
    
for i in range(m):
    if S[B[i]] == 1:
        print("yes")
    else:
        print("no")

Submission status: Accepted

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

def solve(x,y):
    if x==n:
        S[y] = 1
    else:
        solve(x+1,y)
        if y+A[x] < 2001:
            solve(x+1,y+A[x])
            
S = [0]*2001

solve(0,0)
    
for i in range(m):
    if S[B[i]] == 1:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
m = int(input())
B = list(input().split())
for i in range(m):
    B[i] = int(B[i])

def solve(x,y):
    if x==n:
        S[y] = 1
    else:
        solve(x+1,y)
        if y+A[x] < 2001:
            solve(x+1,y+A[x])
            
S = [0 for i in range(2001)]

solve(0,0)
    
for i in range(m):
    if S[B[i]] == 1:
        print("yes")
    else:
        print("no")

Submission status: Accepted

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

max = 2000

def solve(x,y):
    if x==n:
        S[y] = 1
    else:
        solve(x+1,y)
        if y+A[x] < max+1:
            solve(x+1,y+A[x])
            
S = [0 for i in range(max+1)]

solve(0,0)
    
for i in range(m):
    if S[B[i]] == 1:
        print("yes")
    else:
        print("no")

Submission status: Accepted

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

def solve2(x,y):
    if x==n:
        S[y] = 1
    else:
        solve2(x+1,y)
        if y+A[x] < 2001:
            solve2(x+1,y+A[x])
            
S = [0 for i in range(2001)]

solve2(0,0)

def solve(x,y):
    if y<0:
        return False
    elif y==0:
        return True
    elif x==n:
        return False
    else:
        return solve(x+1,y) or solve(x+1,y-A[x])
    
for i in range(m):
    if (i>50 and (S[B[i]] == 1)):
        print("yes")
    elif (i>50 and (S[B[i]] == 0)):
        print("no")
    else:
        if solve(0,B[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()))

box=[]
for i in range(2**n):
	b = '{0:0{1}b}'.format(i,n)
	tmp=[]
	for j in range(n):
		if b[j]=='1':
			if b[j]=='1':
				tmp.append(A[j])
	box.append(sum(tmp))
	
for k in m:
	if k in box:
		print("yes")
	else:
		print("no")

Submission status: Accepted

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

T = [[0]*2001 for i in range(n)]

T[0][0] = 1
T[0][A[0]] = 1
for i in range(1,n):
    for j in range(2001):
        T[i][j] = T[i-1][j]
        if (j - A[i] >=0) and (T[i-1][j-A[i]] == 1):
            T[i][j] = 1
    
for i in range(m):
    if T[n-1][B[i]] == 1:
        print("yes")
    else:
        print("no")

Submission status: Accepted

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

T = [[0]*2001 for i in range(n)]

T[0][0] = 1
T[0][A[0]] = 1
for i in range(1,n):
    for j in range(2001):
        T[i][j] = T[i-1][j]
        if (j - A[i] >=0) and (T[i-1][j-A[i]] == 1):
            T[i][j] = 1
    
for i in range(m):
    if T[n-1][B[i]] == 1: print("yes")
    else: print("no")

Submission status: Accepted

Solution code:
n = int(input())
*X, = map(int, input().split())
m = int(input())
*Y, = map(int, input().split())
 
bits = 1
for a in X:
    bits |= bits << a
 
for m in Y:
    print("yes"*((bits >> m) & 1)or"no")

Submission status: Accepted

Solution code:
n = int(input())
ary = [int(_) for _ in input().split()]
q = int(input())
qs = [int(_) for _ in input().split()]


def search_rec(ind, s, q):
    if ind == n:
        return False
    else:
        tmp = ary[ind]
        if s + tmp == q:
            return True
        else:
            return search(ind + 1, s, q) or search(ind + 1, s + tmp, q)


def search(q):
    sum_ary = [0]

    for i in ary:
        for s in sum_ary:
            if s + i == q:
                return True
        sum_ary += [i + _ for _ in sum_ary]

    else:
        return False


for q in qs:
    if search(q):
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:

import itertools

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

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

sum1=set()

for i in range(1,n+1):
	x=list(itertools.combinations(list1,i))
	for j in x:
		sum1.add(sum(j))
		
		
for i in list2:
	if i in sum1:
		print("yes")
	else:
		print("no")

Submission status: Accepted

Solution code:
# ALDS1_5_A.

def intinput():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a

def binary_search(S, k):
    a = 0; b = len(S) - 1
    if b == 0: return S[0] == k
    while b - a > 1:
        c = (a + b) // 2
        if k <= S[c]: b = c
        else: a = c
    return S[a] == k or S[b] == k

def show(a):
    # 配列aの中身を出力する。
    _str = ""
    for i in range(len(a) - 1): _str += str(a[i]) + " "
    _str += str(a[len(a) - 1])
    print(_str)

def main():
    n = int(input())
    A = intinput()
    q = int(input())
    m = intinput()
    # 配列Aの作る数を調べる。
    nCanMake = [0]
    for i in range(n):
        for k in range(len(nCanMake)):
            x = nCanMake[k] + A[i]
            if not x in nCanMake: nCanMake.append(x)
    # show(nCanMake)
    for i in range(q):
        if m[i] in nCanMake: print("yes")
        else: print("no")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
*A, = map(int, input().split())
q = int(input())
*Q, = map(int, input().split())
 
bits = 1
for a in A:
    bits |= bits << a
 
for q in Q:
    print("yes"*((bits >> q) & 1)or"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, m_i):
    if m_i == 0:
        return True
    if i >= n:
        return False
    res = solve(i + 1, m_i) or solve(i + 1, m_i - a[i])
    return res
 
for m_tmp in m:
    if sum(a) < m_tmp:
        print("no")
    elif solve(0, m_tmp):
        print("yes")
    else:
        print("no")

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def solve(a, m, sumA):
    if m < 0 or m > sumA:
        return False
    if m == 0:
        return True
    if len(a) == 0:
        return False
    return solve(a[1:], m - a[0], sumA) or solve(a[1:], m, sumA)

n = int(input())
tmp = input().split()
a = []
for i in range(n):
    a.append(int(tmp[i]))
q = int(input())
tmp = input().split()
m = []
for i in range(q):
    m.append(int(tmp[i]))

sumA = sum(a)

for i in range(q):
    if solve(a, m[i], sumA):
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
def stdinput():
    from sys import stdin
    return stdin.readline().strip()

def main():
    from itertools import combinations
    n = int(stdinput())
    *A, = map(int, stdinput().split(' '))
    q = int(stdinput())
    *M, = map(int, stdinput().split(' '))

    all_canditee = set([sum(c) for i in range(1, n+1) for c in combinations(A, i)])

    # print(A)
    # print(all_canditee)

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

# can not pass 9/10
def check(m, a, A):
    for i, next_a in enumerate(A):
        this_a = a + next_a
        if this_a == m:
            return True
        elif this_a < m:
            if check(m, this_a, A[i+1:]):
                return True
    return False

if __name__ == '__main__':
    main()
    # import cProfile
    # cProfile.run('main()')

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):
    cache = {}

    def helper(x, y):
        if (x, y) not in cache:
            cache[(x, y)] = f(x, y)
        return cache[(x, y)]
    return helper


def main():
    for number in m:
        if solve(0, number):
            print('yes')
        else:
            print('no')


@memoize
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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    for number in m:
        if solve(0, number):
            print('yes')
        else :
            print('no')

def memolize(f):
    cache = {}

    def helper(x, y):
        if (x, y) not in cache:
            cache[(x, y)] = f(x, y)
        return cache[(x, y)]
    return helper

@memolize
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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
aN = int(input())
A = list(map(int, input().split()))
mN = int(input())
M = list(map(int, input().split()))

def memorize(f) :
    cache = {}
    def helper(*args) :
        if args not in cache :
            cache[args] = f(*args)
        return cache[args]
    return helper

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

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

Submission status: Accepted

Solution code:
def solve(arr, target):
	memo = {}
	return solve_rec(0, arr, target, memo)

def solve_rec(i, arr, target, memo):

	res = False

	key = str(i) + '-' + str(target)
	if key in memo:
		res = memo[key]
	elif target == 0:
		res = True
	elif i >= len(arr):
		res = False
	else:
		res1 = solve_rec(i + 1, arr, target, memo)
		res2 = solve_rec(i + 1, arr, target - arr[i], memo)
		res = res1 or res2

	memo[key] = res		
	return res

n = int(input())
arr = list(map(int, input().split()))
q = int(input())
targets = list(map(int, input().split()))
for i in range(q):
	res = solve(arr, targets[i])
	if res == True:
		print('yes')
	else:
		print('no')

Submission status: Accepted

Solution code:

def solve(arr, target):
	dict = {}
	return solve_rec(0, arr, target, dict)

def solve_rec(i, arr, target, dict):

	res = False

	key = str(i) + '-' + str(target)
	if key in dict:
		res = dict[key]
	elif target == 0:
		res = True
	elif i >= len(arr):
		res = False
	else:
		res1 = solve_rec(i + 1, arr, target, dict)
		res2 = solve_rec(i + 1, arr, target - arr[i], dict)
		res = res1 or res2

	dict[key] = res		
	return res

n = int(input())
arr = list(map(int, input().split()))
q = int(input())
targets = list(map(int, input().split()))
for i in range(q):
	res = solve(arr, targets[i])
	if res == True:
		print('yes')
	else:
		print('no')

Submission status: Accepted

Solution code:

def solve(arr, m):
	dict = {}
	return solve_rec(0, arr, m, dict)

def solve_rec(i, arr, m, dict):
	key = str(i) + '-' + str(m)
	res = False
	if key in dict:
		res = dict[key]
	elif m == 0:
		res = True
	elif i >= len(arr):
		res = False
	else:
		res1 = solve_rec(i + 1, arr, m, dict)
		res2 = solve_rec(i + 1, arr, m - arr[i], dict)
		res = res1 or res2	
	dict[key] = res
	return res

n = int(input())
arr = list(map(int, input().split()))
q = int(input())
targets = list(map(int, input().split()))

for i in range(q):
	res = solve(arr, targets[i])
	if res == True:
		print('yes')
	else:
		print('no')

Submission status: Accepted

Solution code:
def f():
    return int(raw_input())
def f2():
    return map(int, raw_input().split())

def f3(n, AA, x):
    tmp = n + AA[0]
    if len(AA) == 1:
        try: x[tmp] = 1
        except: pass
    else:
        f3(n, AA[1:], x)
        try:
            x[tmp] = 1
            f3(tmp, AA[1:],x)
        except:
            pass
    return

n = f()
A = sorted(f2())
q = f()
M = f2()

x = [0 for i in range(max(M)+1)]
f3(0, A, x)

for e in M:
    if x[e] == 1:
        print 'yes'
    else:
        print 'no'

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
from itertools import combinations


def enum_sum_numbers(sets, s_range, r):
    for cmb in combinations(sets, r):
        yield sum(cmb)
    if r <= s_range:
        for s in enum_sum_numbers(sets, s_range, r+1):
            yield s


stdin.readline()
a = [int(s) for s in stdin.readline().split()]
stdin.readline()
ms = [int(s) for s in stdin.readline().split()]
sets = {s for s in enum_sum_numbers(a, len(a), 1)}

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding:utf-8 -*-
from __future__ import print_function,division
from itertools import combinations
import time
import sys
import io
import re
import math
start = time.clock()
i = 0
def enum_sum_numbers(sets, s_range, r):
    for cmb in combinations(sets,r):
        yield sum(cmb)
    if r <=s_range:
        for s in enum_sum_numbers(sets,s_range, r+1):
            yield s

sys.stdin.readline()
a=[int(s) for s in sys.stdin.readline().split()]
sys.stdin.readline()
ms=[int(s) for s in sys.stdin.readline().split()]
sets={s for s in enum_sum_numbers(a,len(a),1)}
for m in ms:
    print('yes' if m in sets else 'no')

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding:utf-8 -*-
from __future__ import print_function,division
import time
import sys
import io
import re
import math
start = time.clock()
i = 0

sys.stdin.readline()
a=[int(s) for s in sys.stdin.readline().split()]
sys.stdin.readline()
ms=[int(s) for s in sys.stdin.readline().split()]
ans=set([0])
for i in a:
    ans|=set(j+i for j in ans)
ans=list(ans)
for jk in ms:
    if jk in ans: print('yes')
    else: print('no')

Submission status: Accepted

Solution code:
def solve(Mi,i):
	if Mi == 0: return True
	if i < n and min(A[i:]) <= Mi <= sum(A[i:]):
		r1 = solve(Mi-A[i],i+1)
		r2 = solve(Mi,i+1)
		if r1: return r1
		if r2: return r2
n = input()
A = map(int,raw_input().split())
q = input()
M = map(int,raw_input().split())
for Mi in M:
	print "yes" if solve(Mi,0) else "no"

Submission status: Accepted

Solution code:
def solve(Mi,i):
	if Mi == 0: return True
	if i < n and min(A[i:]) <= Mi <= sum(A[i:]):
		r1 = solve(Mi-A[i],i+1)
		if r1: return r1
		r2 = solve(Mi,i+1)
		if r2: return r2
n = input()
A = map(int,raw_input().split())
q = input()
M = map(int,raw_input().split())
for Mi in M:
	print "yes" if solve(Mi,0) else "no"

Submission status: Accepted

Solution code:
def solve(Mi,i):
	if Mi == 0: return True
	if i < n and 0 <= Mi <= sum(A[i:]):
		r1 = solve(Mi-A[i],i+1)
		if r1: return r1
		r2 = solve(Mi,i+1)
		if r2: return r2
n = input()
A = sorted(map(int,raw_input().split()))
q = input()
M = map(int,raw_input().split())
for Mi in M:
	print "yes" if solve(Mi,0) else "no"

Submission status: Accepted

Solution code:
def solve(Mi,i):
	if Mi == 0: return True
	if i < n and A[i] <= Mi <= sum(A[i:]):
		r1 = solve(Mi-A[i],i+1)
		if r1: return r1
		r2 = solve(Mi,i+1)
		if r2: return r2
n = input()
A = sorted(map(int,raw_input().split()))
q = input()
M = map(int,raw_input().split())
for Mi in M:
	print "yes" if solve(Mi,0) else "no"

Submission status: Accepted

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

d = []
for x in range(1 << n):
    b = '{:0{}b}'.format(x, n)
    d.append(sum(a[i] for i in range(n) if b[i] == '1'))

for m in M:
    print('yes' if m in d 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()))
combi = set()

for i in range(1<<n):
    total = 0
    for j in range(n):
        if (i >> j) & 1:
            total += A[j]
    combi.add(total)

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
m = int(input())
q = list(map(int,input().split()))
cand = []
for i in range(2**n):
    tmp = 0
    for j in range(n):
        if(i>>j)&1:
            tmp += a[j]
    if tmp not in cand:
        cand.append(tmp)
for i in q:
    print('yes' if i in cand 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()))

pattern=[]

for i in range(2**n):
    s=0
    for j in range(n):
        if i >> j & 1:
            s+=A[j]
    pattern.append(s)
P=set(pattern)

for m in M:
    print('yes' if m in P 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()))

result = []
# 
for bit in range(1<<n):
    score = 0
    # 
    for i in range((n)):
        # 
        if bit & (1<<i):
            score += a[i]

    result.append(score)

for m_i in m:
    if m_i in result:
        print('yes')
    else :
        print('no')

Submission status: Accepted

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

n = int(input())
A = tuple(int(x) for x in input().split())
_ = int(input())
M = tuple(int(x) for x in input().split())

S = set()
def Check(i, s):
    if i == n:
        S.add(s)
        return
    Check(i + 1, s + A[i])
    Check(i + 1, s)

Check(0, 0)

for m in M:
    if m 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()))
memo = [[-1]*2000 for _ in range(20)]
def solve(i, m):
    if memo[i][m] != -1:
        return memo[i][m]
    if m == 0:
        memo[i][m] = 1
        return True
    if m < 0:
        memo[i][m] = 0
        return False
    if i >= N:
        memo[i][m] = 0
        return False
    if i == N-1:
        memo[i][m] = (A[N-1] == m)
        return (A[N-1] == m)
    res = solve(i+1, m) or solve(i+1, m-A[i])
    memo[i][m] = res
    return res
for mi in m:
    if solve(0, mi):
        print("yes")
    else:
        print("no")

Submission status: Accepted

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

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

existBits = 1

for a in A:
    existBits |= existBits << a
        
if(__name__ == '__main__'):
    
    for m in M:
        
        judge = (existBits << m)
        
        if(((existBits >> m) & 1) == 1):
            print("yes")
        else:
            print("no")

Submission status: Accepted

Solution code:
#Exhaustive Search (bit全探索ver)
n = int(input())
A = list(map(int,input().split()))
q = int(input())
m = list(map(int,input().split()))

count_list = []
for i in range(1<<n):
    copy_A = A.copy()
    count = 0
    for j in range(n):
        mask = 1 << j
        if mask & i != 0:
            count += A[j]
    count_list.append(count)

for k in m:
    if k in count_list:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
from functools import lru_cache

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


@lru_cache(maxsize=2**12)
def makeCombination(i,key):
    if key == 0:
        return True
    if i == n:
        return False
    return makeCombination(i+1,key) or makeCombination(i+1,key-A[i])


for m in M:
    if makeCombination(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()))
q = int(input())
m = list(map(int, input().split()))


answer = ['no']*q
for i in range(1, n+1):
    for nums in combinations(a, i):
        val = sum(nums)
        if val in m:
            index = [i for i, num in enumerate(m) if val == num]
            for i in index:
                answer[i] = 'yes'

for i in answer:
    print(i)

Submission status: Accepted

Solution code:
def calc(s, i):
    global n
    global anslst
    global nlst
    if i == n:
        anslst[s] = 'yes'
        return

    calc(s, i+1)
    calc(s + nlst[i], i+1)


anslst = ['no']*2001
n = int(input())
nlst = list(map(int, input().split()))
q = int(input())
qlst = list(map(int, input().split()))

calc(0, 0)

for i in qlst:
    print(anslst[i])

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()))

ANS = set()
for i in range(1,n+1):
    A_pairs = list(itertools.combinations(A, i))
    for j in range(len(A_pairs)):
        ANS.add(sum(A_pairs[j]))

for i in range(q):
    if m[i] in ANS:
        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()))

S = set([])
for i in range(2<<n):
    num = 0
    for j in range(n):
        bit = (i>>j) & 1
        num += bit * A[j]
    S.add(num)

for m in M:
    if m in S:
        print('yes')
        continue
    print('no')

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
q = int(input())
L = list(map(int, input().split()))
X = list()
for bit in range(1<<n):
  A2 = list()
  for i in range(n):
    if bit & (1<<i):
      A2.append(A[i])
  X.append(sum(A2))
for i in range(q):
  if L[i] in X:
    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()))

ans_map = {}

for i in range(1, n * 2000 + 1):
    ans_map[i] = 0

for i in range(2 ** n - 1):
    str_i = str(bin(i)[2:]).zfill(n)
    sum_a = 0
    for j, bit in enumerate(str_i):
        if bit == '1':
            sum_a += A[j]
    ans_map[sum_a] = 1

for m in M:
    if ans_map[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()))

d={}
for i in range(2**n):
    c=0
    for j in range(n):
        if (i>>j)&1:
            c+=a[j]
    d[c]=1

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

Submission status: Accepted

Solution code:
import itertools as it

n, A = int(input()), [*map(int, input().split())]
yes_nums = set()
for bools in it.product([True, False], repeat=n):
  yes_nums.add(sum(A[i] for i in range(n) if bools[i]))

_ = input()
for m in map(int, input().split()):
  print("yes" if m in yes_nums 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()))

d = {}

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

for m in M:
    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())
b = list(map(int,input().split()))

sumn = {0}
for i in a:
    sumn |= {i + x for x in sumn}
for i in b:
    if i in sumn:
        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(x,y):
    global n
    global A
    if y==0:
        return True
    if x>=n:
        return False
    if sum(A[x:])<y:
        return False
    return solve(x+1,y) or solve(x+1,y-A[x])
for i in m:
    if solve(0,i):
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
from itertools import combinations
n=int(input())
a=list(map(int,input().split()))
q=int(input())
m=list(map(int,input().split()))

s=set()
for i in range(1,n+1):
    for j in combinations(a,i):
        s.add(sum(j))
for i in m:
    if i in s:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
# get n  list_n
n = int(input())
list_n = [int(x) for x in input().split(' ')]

# get q list_q
q = int(input())
list_q = [int(x) for x in input().split(' ')]

#define recursion find_partial_sum
#input: integer list and M
#output boolean

def find_partial_sum(idx, M):
    if 0 > M or idx >= n:
        return False
    i = list_n[idx]
    if M == i:
        return True
    if find_partial_sum(idx+1, M-i) or find_partial_sum(idx+1, M):
        return True
    return False
#iterate q and check find_åparcial_sum(list_n, q_i) and print
for q_i in list_q:
    if sum(list_n) < q_i:
        print("no")
    elif find_partial_sum(0, q_i):
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
N=int(input())
*A,=map(int,input().split())
Q=int(input())
*M,=map(int,input().split())
mf=['no']*Q
t=[]
for i in range(0,2**N):
    ans=0
    for j in range(N):
        if (i>>j&1):
            ans+=A[j]
    t.append(ans)
tset=set(t)

for i in range(Q):
    if M[i] in tset:
        mf[i] = 'yes'

for i in mf:
    print(i)

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()))

# メイン処理
ans_list = ["no" for i in range(q)]
for bit in range(1 << n):
    s = 0
    for i in range(n):
        if bit & (1 << i):
            s += A[i]
    L = [i for i, x in enumerate(m) if x == s]
    for l in L:
        ans_list[l] = "yes"

# 結果出力
for ans in ans_list:
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
*li, = map(int, input().split())
input()
*Q, = map(int, input().split())

bits = 1
for i in li:
    # print(f"{i=}")
    # print(f"{bin(bits)=}")
    bits |= bits << i
    # print(f"{bin(bits)=}")
    # print()

# print()
for q in Q:
    # print(f"{bin(bits)=}")
    print("yes"*((bits >> q) & 1) or "no")
    # print()

Submission status: Accepted

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

values = set({})
for num in range(1 << n):
    count = 0
    for k in range(n):
        if num & (1 << k) == 1 << k:
            count += A[k]
    # print(num, count)
    values.add(count)

m = int(input())
Q = list(map(int, input().split()))
for q in Q:
    if q in values:
        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()))
b=[0]*2**n
for i in range(2**n):
  tr=bin(i)[2:].zfill(n)
  cnt=0
  for j in range(n):
    if tr[j]=='1':
      cnt+=a[j]
  b[i]=cnt
for i in m:
  if i in b:
      print('yes')
  else:
      print('no')

Submission status: Accepted

Solution code:
from functools import lru_cache

num = int(input())
arr = list(map(int, input().split()))
question_nums = int(input())
questions = list(map(int, input().split()))

@lru_cache(maxsize=2**12)
def solve(index, total):
    if total == 0:
        return True
    if index == num:
        return False
    return solve(index+1, total - arr[index]) or solve(index+1, total)

for q in questions:
    if solve(0, q):
        print("yes")
    else:
        print("no")

Submission status: Accepted

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

dp = [[False for i in range(4300)]for i in range(2)]
dp[0][0] = True
dp[1][0] = True
c = False
for i in a:
    for j in range(4000):
        if dp[c][j]:
            dp[not(c)][j+i] = True
            dp[not(c)][j] = True
    c = not(c)

for i in b:
    if dp[c][i]:
        print("yes")
    else:
        print("no")

# print(dp[c][:20])

Submission status: Accepted

Solution code:
def exhaustiveSearch(A:list, m:int) -> str:
    if m == 0:
        return True
    if len(A) == 0 or sum(A) < m:
        return False
    return exhaustiveSearch(A[1:], m) or exhaustiveSearch(A[1:], m - A[0])
    


if __name__ == '__main__':
    n = int(input())
    A = list(map(int, input().rstrip().split()))
    q = int(input())
    M = list(map(int, input().rstrip().split()))
    for m in M:
        if exhaustiveSearch(A, m):
            print('yes')
        else:
            print('no')