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: Wrong Answer

Solution code:
n=int(input())
A=[0 for i in range(n)]
A=input().split()
for i in range(n):
    A[i]=int(A[i])
q=int(input())
B=[0 for i in range(q)]
B=input().split()
C=[]
for i in range(q):
    B[i]=int(B[i])
    c=0
    for j in range(n-1):
        for k in range(j+1,n):
            sum=A[j]+A[k]
            if sum==B[i] and c==0:
                c+=1
                C.append("yes")
    if c==0:
        C.append("no")
for i in range(q):
    print(C[i])

Submission status: Wrong Answer

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

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

A.sort()

for i in range(m):
    cnt=0
    for j in range(n):
        if cnt==0:
            for k in range(n-j-1):
                m=A[j]+A[n-k-1]
                if m==B[i]:
                    print("yes")
                    cnt=1
                elif m<B[i]:
                    break
    if cnt==0:
        print("no")

Submission status: Wrong Answer

Solution code:
import itertools as itl

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

for mi in M:
    flg = False
    for i in range(len(A)):
        C = itl.combinations(A, i)
        print(C)
        for j in C:
            if sum(j) == mi:
                flg = True
                break
    if flg: print("yes")
    else: print("no")

Submission status: Wrong Answer

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

for h in range(q):
    cnt=0
    for i in range(n+1):
        for j in it.combinations(A,i):
            print(sum(j))
            if sum(j)==m[h]:
                cnt = 1
    if cnt==1:
        print("yes")
    else:
        print("no")

Submission status: Wrong Answer

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

for h in range(q):
    cnt=0
    for i in range(n):
        for j in it.combinations(A,i):
            print(sum(j))
            if sum(j)==m[h]:
                cnt = 1
    if cnt==1:
        print("yes")
    else:
        print("no")

Submission status: Wrong Answer

Solution code:
def solve_knapsack_problem(A,n,m):
    a=[[0 for i in range(m+1)]for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,m+1):
            if A[i-1]>j:
                a[i][j] = a[i-1][j]
            else:
                a[i][j] = a[i-1][j-A[i-1]]+A[i-1]
            if a[i][j] == m:
                return True
    return False

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

    for i in range(q):
        if solve_knapsack_problem(A,n,m[i]):
            print("yes")
        else:
            print("no")

Submission status: Wrong Answer

Solution code:
def solve_knapsack_problem(A,n,m):
    a=[[0 for i in range(m+1)]for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,m+1):
            if A[i-1]<=j:
                a[i][j] = a[i-1][j-A[i-1]]+A[i-1]
            else:
                a[i][j] = a[i-1][j]
            
            if a[i][j] == m:
                return True
    print(a)
    return False

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

    for i in range(q):
        if solve_knapsack_problem(A,n,m[i]):
            print("yes")
        else:
            print("no")

Submission status: Wrong Answer

Solution code:
def solve_knapsack_problem(A,n,m):
    a=[[0 for i in range(m+1)]for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,m+1):
            if A[i-1]>j:
                a[i][j] = a[i-1][j]
            else:
                a[i][j] = a[i-1][j-A[i-1]]+A[i-1]
            
            if a[i][j] == m:
                return True

    return False

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

    for i in range(q):
        if solve_knapsack_problem(A,n,m[i]):
            print("yes")
        else:
            print("no")

Submission status: Wrong Answer

Solution code:
def solve_knapsack_problem(A,n,m):
    a=[[0 for i in range(m+1)]for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,m+1):
            if A[i-1]<=j:
                a[i][j] = a[i-1][j-A[i-1]]+A[i-1]
            else:
                a[i][j] = a[i-1][j]
            
            if a[i][j] == m:
                return True

    return False

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

    for i in range(q):
        if solve_knapsack_problem(A,n,m[i]):
            print("yes")
        else:
            print("no")

Submission status: Wrong Answer

Solution code:
def solve_knapsack_problem(A,n,m):
    a=[[0 for i in range(m+1)]for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(0,m+1):
            if A[i-1]<=j:
                a[i][j] = a[i-1][j-A[i-1]]+A[i-1]
            else:
                a[i][j] = a[i-1][j]
            
            if a[i][j] == m:
                return True
    return False

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

    for i in range(q):
        if solve_knapsack_problem(A,n,m[i]):
            print("yes")
        else:
            print("no")

Submission status: Wrong Answer

Solution code:
def solve_knapsack_problem(A,n,m):
    a=[[0 for i in range(m+1)]for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,m+1):
            if A[i-1]<=j:
                a[i][j] = a[i-1][j-A[i-1]]+A[i-1]
            else:
                a[i][j] = a[i-1][j]
            
            if a[i][j] == m:
                return True
    return False

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

    for i in range(q):
        if solve_knapsack_problem(A,n,m[i]):
            print("yes")
        else:
            print("no")

Submission status: Wrong Answer

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

for i in range(0,m+1):
    for j in range(i+1,m+1):
        if i==j:
            break
        ans=A[i]+A[j]
        A.append(ans)

print(A)
print(B)

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

Submission status: Wrong Answer

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

for i in range(0,n):
    for j in range(i+1,n):
        if i==j:
            break
        ans=A[i]+A[j]
        C.append(ans)

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

Submission status: Wrong Answer

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

for i in range(0,n):
    for j in range(i+1,n):
        if i==j:
            break
        ans=A[i]+A[j]
        A.append(ans)

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

Submission status: Wrong Answer

Solution code:
import itertools as itl

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

C = [False for i in range(q)]
for i in range(1, n+1):
    for j in itl.combinations(A, i):
        for mi in range(q):
            if sum(j) == M[mi]:
                C[mi] = True
                break
                
for c in C:
    if c: print("yes")
    else: print("no")

Submission status: Wrong Answer

Solution code:
import itertools as itl

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

C = [False for i in range(q)]
for i in range(1, n+1):
    for j in itl.combinations(A, i):
        for mi in range(q):
            if sum(j) == M[mi]:
                C[mi] = True
                break
        if True in C: break
    if False in C: pass
    else: break
    
for c in C:
    if c: print("yes")
    else: print("no")

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[]*n
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])
f=[[0 for j in range(n)]for i in range(n)]
for i in range(m):
    flag=0
    for j in range(n):
        for k in range(n):
            if j<k:
                tmp=A[j]+A[k]
                if tmp==B[i]:
                    print("yes")
                    flag=1
                    break
                else: pass
            else: pass
        if flag==1: 
            break
        else: pass
    if flag==0:
        print("no")
    else: pass

Submission status: Wrong Answer

Solution code:

n=int(input())
list1=[int(x) for x in input().split()]

q=int(input())
list2=[int(x) for x in input().split()]

for i in range(len(list2)):
	ok=0
	for k in range(len(list1)-1):
		if ok==1:
			break
		for l in range(1,len(list1)):
			if list1[k]+list1[l]==list2[i]:
				print("yes")
				ok=1
				break
	if ok==0:
		print("no")

Submission status: Wrong Answer

Solution code:

n=int(input())
list1=[int(x) for x in input().split()]

q=int(input())
list2=[int(x) for x in input().split()]

for i in range(len(list2)):
	ok=0
	for k in range(len(list1)-1):
		if ok==1:
			break
		for l in range(1,len(list1)):
			if list1[k]+list1[l]==list2[i] or list1[k]==list2[i] or list1[l]==list2[i]:
				print("yes")
				ok=1
				break
	if ok==0:
		print("no")

Submission status: Wrong Answer

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

for m_i in m:

	flag=0
	
	for i in range(2,n+1):
	
		for c in it.combinations(A,i):
		
			if sum(c)==m_i:
				flag=1
				break
		
		if flag==1:
			break
	
	if flag==1:
		print("yes")
	else:
		print("no")

Submission status: Wrong Answer

Solution code:
import itertools as it
n=int(input())
A=list(map(int,input().split()))
q=int(input())
m=list(map(int,input().split()))
ans=[]
for m_i in m:

	flag=0
	
	for i in range(2,n+1):
	
		for c in it.combinations(A,i):
		
			if sum(c)==m_i:
				flag=1
				break
		
		if flag==1:
			break
	
	if flag==1:
		ans.append("yes")
	else:
		ans.append("no")

for a in ans:
	print(a)

Submission status: Wrong Answer

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 y<0:
        return False
    elif y==1:
        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 solve(0,B[i]):
        print("yes")
    else:
        print("no")

Submission status: Wrong Answer

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: Wrong Answer

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: Wrong Answer

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 - B[i] >=0) and (T[i-1][j-B[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: Wrong Answer

Solution code:
def rec(x,y):
    for i in range(len(x)):
        if x[i]>y:
            return "no"
        for j in range(len(x)):
            if i!=j:
                if x[i]+x[j]==y:
                    return "yes"
n=int(input())
A=list(map(int,input().split(' ')))
p=int(input())
m=list(map(int,input().split(' ')))
A.sort()
for i in range(len(m)):
    print(rec(A,m[i]))

Submission status: Wrong Answer

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

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

x = [0 for i in range(q)]

for i in range(q):
	for j in range(n-1):
		for k in range(j+1,n):
			if int(A[k]) == int(m[i]) - int(A[j]):
				x[i]=1
				break

	if x[i] == 1:
		print("yes")
	else:
		print("no")

Submission status: Wrong Answer

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 = []
    for i in range(n):
        if not A[i] in nCanMake: nCanMake.append(A[i])
        if i > 0:
            for k in range(len(nCanMake)):
                x = nCanMake[k] + A[i]
                if not x in nCanMake: nCanMake.append(x)
    nCanMake.sort()
    for i in range(q):
        if m[i] in nCanMake: print("yes")
        else: print("no")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 i >= n:
        res = False
    elif m == 0:
        res = True
    else:
        res = solve(i+1, m) or solve(i+1, m-A[i])
    return res

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

Submission status: Wrong Answer

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

def main():
    n = int(stdinput())
    A = list(sorted(map(int, stdinput().split(' ')), reverse=True))
    q = int(stdinput())
    M = list(map(int, stdinput().split(' ')))

    for m in M:
        if check(m, 0, list(filter(lambda a: a < m, A))):
            print('yes')
        else:
            print('no')

def check(m, a, A):
    # print(f'{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: Wrong Answer

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: Wrong Answer

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

n = f()
A = f2()
q = f()
M = f2()
maxm = max(M)
x = [0 for i in range(maxm+1)]
for i in range(n):
    for j in range(i+1,n):
        p = A[i] + A[j]
        if p > maxm: break
        x[p] = 1

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

Submission status: Wrong Answer

Solution code:
def f():
    return int(raw_input())
def f2():
    return sorted(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 = 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: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def solve(Mi,i):
	if Mi == 0: return True
	if i < n and 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: Wrong Answer

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)
		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: Wrong Answer

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)
    print(b)
    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: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))
def rec(i, m):
    if m == 0:
        return True
    if i >= n:
        return False
    res = rec(i + 1, m) | rec(i + 1, m - A[i])
    return res
for m in M:
    if rec(0, m):
        print('yes')
    else:
        print('no')

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))
def rec(i, m):
    if m == 0:
        return True
    if i >= n:
        return False
    res = rec(i + 1, m)
    if m - A[i] >= 0:
        res |= rec(i + 1, m - A[i])
    return res
for m in M:
    if rec(0, m):
        print('yes')
    else:
        print('no')

Submission status: Time Limit Exceeded

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

def deci_to_bin_list(num, n):
    out = [0]*n
    for i in range(n-1, -1, -1):
        denom = 2**i
        out[i] = num // denom
        num = num % denom
    return out

def sum_selected(A, selected):
    sum = 0
    for a,b in zip(A, selected):
        sum += a*b
    return sum

def sums_to_num(A, num):
    n = len(A)
    for cnt in range(2**n - 1):
        selected = deci_to_bin_list(cnt, n)
        if sum_selected(A, selected) == num:
            return 'yes'
    return 'no'

for num in m:
    print(sums_to_num(A, num))

Submission status: Time Limit Exceeded

Solution code:
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
    else:
        return solve(i+1, m) or solve(i+1, m - A[i])
    

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

Submission status: Time Limit Exceeded

Solution code:
def subset_sum(s, a):
	return subset_rec(0, s, a)
	
def subset_rec(i, s, a):
	if s == 0:
		return True
	if i >= len(a):
		return False
	return subset_rec(i+1, s-a[i], a) or subset_rec(i+1, s, a)	

n = int(input())
a = list(map(int, input().split()))
p = int(input())
q = list(map(int, input().split()))
for i in range(p):
	if subset_sum(q[i], a):
		print('yes')
	else:
		print('no')

Submission status: Time Limit Exceeded

Solution code:
def can_construct_q(q, array, i, sum_sofar):
    if sum_sofar == q or sum_sofar + array[i] == q:
        return True
    elif sum_sofar > q or i >= len(array) - 1:
        return False
    if can_construct_q(q, array, i + 1, sum_sofar + array[i]):
        return True
    if can_construct_q(q, array, i + 1, sum_sofar):
        return True


def main():
    input()
    array_a = list(map(int, input().split()))
    input()
    array_q = map(int, input().split())
    for q in array_q:
        if can_construct_q(q, array_a, 0, 0):
            print('yes')
        else:
            print('no')
    return


main()

Submission status: Time Limit Exceeded

Solution code:
def solve(i,m):
    if m == 0:
        return True
    if i == n:
        return False
    else:
        return solve(i+1,m) | solve(i+1,m-n_list[i])


n = int(input())
n_list = list(map(int,input().split()))
q = int(input())
q_list = list(map(int,input().split()))

for num in q_list:
    print('yes') if solve(0,num) else print('no')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

"""
全探索
・再帰で作る
"""

N = int(input())
aN = list(map(int, input().split()))
Q = int(input())
mQ = list(map(int, input().split()))

def dfs(cur, depth, ans):
    # 終了条件
    if cur == ans:
        return True
    # 全探索
    for i in range(depth, N):
        if dfs(cur+aN[i], i+1, ans):
            return True
    # 見つからなかった
    return False

for i in range(Q):
    if dfs(0, 0, mQ[i]):
        print('yes')
    else:
        print('no')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

"""
全探索
・ビットでやる
"""

N = int(input())
aN = list(map(int, input().split()))
Q = int(input())
mQ = list(map(int, input().split()))

for i in range(Q):
    # 全組み合わせ2^Nのループ
    for j in range(1 << N):
        sm = 0
        for k in range(N):
            # 各ビットについて、立っていればその位置の値を加算
            if j >> k & 1:
                sm += aN[k]
        if sm == mQ[i]:
            print('yes')
            break
    else:
        print('no')

Submission status: Time Limit Exceeded

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

n = int(input())
n_list = list(map(int,input().split()))
q = int(input())
q_list = list(map(int,input().split()))

for num in q_list:
    print('yes') if brute(0,num) else print('no')

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = int(input())
c = list(map(int, input().split()))
e = []
for i in range(2**n):
    d = []
    for j in range(n):
        if (i>>j)&1:
            d.append(a[j])
            e.append(sum(d))

for k in c:
    if k in e:
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

for m in M:
    ans = 'no'
    for i in range(1, n + 1):
        for c in itertools.combinations(A, i):
            #print(c)
            if sum(list(c)) == m:
                ans = 'yes'
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def branch(array, p, m):
    if p == len(array):
        return m == sum(array)

    array2 = array[:p] + [0] + array[p+1:]
    r = branch(array, p+1, m)
    l = branch(array2, p+1, m)
    if r or l:
        return True
    else:
        return False

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

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

Submission status: Time Limit Exceeded

Solution code:
def branch(array, p, m):
    if sum(array[:p]) > m:
        return False

    if p == len(array):
        return m == sum(array)

    array2 = array[:p] + [0] + array[p+1:]
    r = branch(array, p+1, m)
    l = branch(array2, p+1, m)
    if r or l:
        return True
    else:
        return False

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

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

Submission status: Time Limit Exceeded

Solution code:
def branch(array, b, p, m):
    if p == len(array):
        return m == sum(array[i] for i in range(p) if b[i] == 1)

    b2 = b[:p] + [0] + b[p+1:]
    r = branch(array, b, p+1, m)
    l = branch(array, b2,  p+1, m)
    if r or l:
        return True
    else:
        return False

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

for m in M:
    b = [1] * n
    print('yes' if branch(A, b, 0, m) else 'no')

Submission status: Time Limit Exceeded

Solution code:
def branch(array, b, p, m):
    if p == len(array):
        return m == sum(array[i] for i in range(p) if b[i] == 1)

    b2 = b[:p] + [0] + b[p+1:]
    r = branch(array, b, p+1, m)
    l = branch(array, b2,  p+1, m)
    if r or l:
        return True
    else:
        return False

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

for m in M:
    b = [1] * n
    print 'yes' if branch(A, b, 0, m) else 'no'

Submission status: Time Limit Exceeded

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

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 soleve(0, m, A):
        print 'yes'
    else:
        print 'no'

Submission status: Time Limit Exceeded

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

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 soleve(0, m, A, n):
        print 'yes'
    else:
        print 'no'

Submission status: Time Limit Exceeded

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

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


q = int(raw_input())
M = map(int, raw_input().split())
for m in M:
    if soleve(0, m, n):
        print 'yes'
    else:
        print 'no'

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
A = map(int, raw_input().split())
result = []

def soleve(i, m, n):
    if m == 0:
        return True
    if i >= n:
        return False
    a = soleve(i + 1, m, n)
    b = soleve(i + 1, m - A[i], n)
    if a:
        result.append(m)
    if b:
        result.append(m - A[i])
    return a or b


q = int(raw_input())
M = map(int, raw_input().split())
for m in M:
    if m in result:
        print 'yes'
    elif soleve(0, m, n):
        print 'yes'
    else:
        print 'no'

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
A = map(int, raw_input().split())
d = {}
def soleve(i, m):
    if (i, m) in d.keys():
        return d[(i, m)]
    if m == 0:
        return True
    if i >= n:
        return False
    a = soleve(i + 1, m)
    d[(i+1, m)] = a
    b = soleve(i + 1, m - A[i])
    d[(i+1, m-A[i])] = b
    return a or b


q = int(raw_input())
M = map(int, raw_input().split())
for m in M:
    if soleve(0, m):
        print 'yes'
    else:
        print 'no'

Submission status: Time Limit Exceeded

Solution code:
import sys


def search_combination(elements, target):
    if len(elements) == 0:
        if target == 0:
            return True
        else:
            return False

    return search_combination(elements[1:], target - elements[0]) or search_combination(elements[1:], target)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    elements = [int(x) for x in lines[1].strip().split(" ")]
    targets = [int(x) for x in lines[3].strip().split(" ")]

    for target in targets:
        result = "yes" if search_combination(elements, target) else "no"
        print(result)