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:
# -*- coding: utf-8 -*-

import random
import sys
import os
import pprint

#fd = os.open('ALDS1_5_A.txt', os.O_RDONLY)
#os.dup2(fd, sys.stdin.fileno())

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

# memo table T[i][m]
row_num = len(A)
column_num = 2000
T = [[None for i in range(column_num)] for j in range(row_num)]
#pprint.pprint(T)


def solve(i, m):
    # out of index
    if i >= len(A):
        return False
    if m < 0:
        return False

    if T[i][m] is not None:
        return T[i][m]

    if m == 0:
        T[i][m] = True
    #elif i >= len(A):
    #    T[i][m] = False
    elif solve(i+1, m):
        T[i][m] = True
    elif solve(i+1, m - A[i]):
        T[i][m] = True
    else:
        T[i][m] = False
    return T[i][m]

test_num = int(input())
test_values = map(int, input().split())
for v in test_values:
    result = solve(0, v)
    if result is True:
        print('yes')
    else:
        print('no')

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
N = int(2**n)
d = []

for i in range(N):
    b = "{:0{}b}".format(i, n)
    d.append(sum(A[j] for j in range(n) if b[j] == '1'))

    #print(b)

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

Submission status: Wrong Answer

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

import sys
import os


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

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

def solve(i, m):
    #print('i', i, 'm', m)

    # i????????\???????????????????????£???m??????????????¨???true
    # i = 0, ..., n-1
    if i >= n:
        return False
    elif m == 0:
        return True
    else:
        # Devide and Conquer

        # i??????????????°??????
        res0 = solve(i + 1, m)
        # i??????????????¶
        res1 = solve(i + 1, m - A[i])

        if res0 or res1:
            return True
        else:
            return False


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

Submission status: Wrong Answer

Solution code:
import sys
from itertools import product
from operator import add


n = int(sys.stdin.readline())
As = list(map(int, sys.stdin.readline().split()))
q = int(sys.stdin.readline())
Ms = tuple(map(int, sys.stdin.readline().split()))


def solve(arr):
    arr.sort()
    sol = set()
    while len(arr) > 1:
        h, arr = arr[0], arr[1:]
        sol = sol.union(set(map(lambda x: add(*x), product(sol, [h])))).union(set(map(lambda x: add(*x), product(arr, [h]))))

    return map(lambda x: 'yes' if x else 'no', map(lambda x: x in sol, Ms))

for s in solve(As):
    print(s)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import product
from operator import add


n = int(sys.stdin.readline())
As = list(map(int, sys.stdin.readline().split()))
q = int(sys.stdin.readline())
Ms = tuple(map(int, sys.stdin.readline().split()))


def solve(arr):
    arr.sort()
    sol = set()
    while len(arr) > 1:
        h, arr = arr[0], arr[1:]
        sol = sol.union(
            set(map(lambda x: add(*x), product(sol, [h])))
        ).union(set(map(lambda x: add(*x), product(arr, [h]))))
    sol = sol.union(As)
    return map(lambda x: 'yes' if x else 'no', map(lambda x: x in sol, Ms))

for s in solve(As):
    print(s)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import product
from operator import add


n = int(sys.stdin.readline())
As = list(map(int, sys.stdin.readline().split()))
q = int(sys.stdin.readline())
Ms = tuple(map(int, sys.stdin.readline().split()))


def solve(arr):
    arr = sorted(list(set(arr)))
    sol = set()
    while len(arr) > 1:
        h, arr = arr[0], arr[1:]
        sol = sol.union(
            set(map(lambda x: add(*x), product(sol, [h])))
        ).union(set(map(lambda x: add(*x), product(arr, [h]))))
    print(As)
    sol = sol.union(As)
    return map(lambda x: 'yes' if x else 'no', map(lambda x: x in sol, Ms))

for s in solve(As):
    print(s)

Submission status: Wrong Answer

Solution code:

import sys
from itertools import product
from operator import add


n = int(sys.stdin.readline())
As = list(map(int, sys.stdin.readline().split()))
q = int(sys.stdin.readline())
Ms = tuple(map(int, sys.stdin.readline().split()))


def solve(arr):
    arr = sorted(list(set(arr)))
    sol = set()
    while len(arr) > 1:
        h, arr = arr[0], arr[1:]
        sol = sol.union(
            set(map(lambda x: add(*x), product(sol, [h])))
        ).union(set(map(lambda x: add(*x), product(arr, [h]))))    
    sol = sol.union(As)
    return map(lambda x: 'yes' if x else 'no', map(lambda x: x in sol, Ms))

for s in solve(As):
    print(s)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import product
from operator import add


n = int(sys.stdin.readline())
As = list(map(int, sys.stdin.readline().split()))
q = int(sys.stdin.readline())
Ms = tuple(map(int, sys.stdin.readline().split()))


def solve(arr):
    arr = sorted(list(set(arr)))
    sol = set()
    while arr:
        h, arr = arr[0], arr[1:]
        sol = sol.union(
            set(map(lambda x: add(*x), product(sol, [h])))
        ).union(set(map(lambda x: add(*x), product(arr, [h]))))
    sol = sol.union(As)
    return map(lambda x: 'yes' if x else 'no', map(lambda x: x in sol, Ms))

for s in solve(As):
    print(s)

Submission status: Wrong Answer

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

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

def f(A, s, res):
  if res[0]:
    return
  if s == 0:
    res[0] = True
    return
  for a in reversed(A):
    if a <= s:
      f(A[0:A.index(a)], s-a, res)

for mi in m:
  res = [False]
  f(A, mi, res)
  if res[0]:
    print("yes")
  else:
    print("no")

Submission status: Wrong Answer

Solution code:
def solve(A, m):
	if m<0 or len(A)==0:
		return False
	if m == 0:
		return True
	else:
		no_use = solve(A[1:], m-int(A[0]))
		if no_use:
			return True
		else:
			return solve(A[1:], m)

def main():
	n = int(input())
	A = input()
	A = A.split()
	q = int(input())
	ms= input()
	for m in ms.split():
		if solve(A, int(m)):
			print('yes')
		else:
			print('no')

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:

def solve(A, ms, flags, indexs):
	for i,m in zip(indexs, ms):
		if m==0:
			flags[i]=True
			indexs.pop(i)
			ms.pop(i)
	if len(A)==0:
		return flags
	else:
		use = solve(A[1:], list(map(lambda x:x-A[0], ms)), flags, indexs)
		no_use = solve(A[1:], ms, flags, indexs)
		return list(map(lambda x,y:x or y, use, no_use))

def main():
	n = int(input())
	A = input()
	A = list(map(int, A.split()))
	q = int(input())
	m = input()
	m = list(map(int, m.split()))
	flags = [False for i in range(q)]
	indexs = list(range(q))
	for flag in solve(A, m, flags, indexs):
		if flag:
			print('yes')
		else:
			print('no')

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:

def solve(A, ms, flags):
	if 0 in ms:
		i = ms.index(0)
		flags[i]=True

	if len(A)==0:
		return flags
	else:
		use = solve(A[1:], list(map(lambda x:x-A[0], ms)), flags)
		no_use = solve(A[1:], ms, flags)
		return list(map(lambda x,y:x or y, use, no_use))

def main():
	n = int(input())
	A = input()
	A = list(map(int, A.split()))
	q = int(input())
	m = input()
	m = list(map(int, m.split()))
	flags = [False for i in range(q)]
	for flag in solve(A, m, flags):
		if flag:
			print('yes')
		else:
			print('no')

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:

def solve(A, ms, flags):
	if 0 in ms:
		i = ms.index(0)
		flags[i]=True
		ms[i]=-1

	if len(A)==0:
		return flags
	else:
		use = solve(A[1:], list(map(lambda x:x-A[0], ms)), flags)
		no_use = solve(A[1:], ms, flags)
		return list(map(lambda x,y:x or y, use, no_use))

def main():
	n = int(input())
	A = input()
	A = list(map(int, A.split()))
	q = int(input())
	m = input()
	m = list(map(int, m.split()))
	flags = [False for i in range(q)]
	for flag in solve(A, m, flags):
		if flag:
			print('yes')
		else:
			print('no')

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:

def solve(A, ms, flags, index):
	if len(A)==0:
		return flags
	else:
		now_ms = [m for m in ms if m >= 0]
		now_index = [i for i,m in zip(index,ms) if m >= 0]
		while 0 in now_ms:
			i = now_ms.index(0)
			flags[now_index[i]]=True
			now_index.pop(i)
			now_ms.pop(i)

		use = solve(A[1:], list(map(lambda x:x-A[0], now_ms)), flags, now_index)
		no_use = solve(A[1:], now_ms, flags, now_index)
		return list(map(lambda x,y:x or y, use, no_use))

def main():
	n = int(input())
	A = input()
	A = list(map(int, A.split()))
	q = int(input())
	m = input()
	m = list(map(int, m.split()))
	flags = [False for i in range(q)]
	index = list(range(q))
	for flag in solve(A, m, flags,index):
		if flag:
			print('yes')
		else:
			print('no')

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
class MyClass():
    def main(self):
        self.n = input()
        self.A = map(int,raw_input().split())
        self.q = input()
        self.M = map(int,raw_input().split())
        
        W = map(self.solve,self.M)
        for w in W:
            print w

    def solve(self,m):
        w = self.rec(m,self.A)
        if w:
            return "yes"
        else:
            return "no"

    def rec(self,m,A):
        if len(A) == 1:
            r1 = False
        else:
            r1 = self.rec(m,A[1:])

        m_new = m - A[0]
        if m_new == 0:
            r2 = True
        elif len(A) > 1 and min(A[1:]) <= m <= sum(A[1:]):
            r2 = self.rec(m_new,A[1:])
        else:
            r2 = False

        if r1 or r2:
            return True
        else:
            return False

if __name__ == "__main__":
    MC = MyClass()
    MC.main()

Submission status: Wrong Answer

Solution code:
import bisect
n = int(input())
A = tuple(map(int,input().split()))
q = int(input())
Q = tuple(map(int, input().split()))
l = 2**n
dp = [0]*(l)

for i in range(n):
    for j in range(1<<i):
        dp[j+(1<<i)] = dp[j] + A[i]

for n in Q:
    i = bisect.bisect(dp, n)
    print("yes" if l>0 and n==dp[i-1] else "no")

Submission status: Wrong Answer

Solution code:
import bisect
n = int(input())
A = tuple(map(int,input().split()))
q = int(input())
Q = tuple(map(int, input().split()))
dp = [0]*(2**n)

for i in range(n):
    for j in range(1<<i):
        dp[j+(1<<i)] = dp[j] + A[i]

for n in Q:
    i = bisect.bisect(dp, n)
    print("yes" if i>0 and n==dp[i-1] else "no")

Submission status: Wrong Answer

Solution code:
import itertools


def rev(x):
    return sumA - x


if __name__ == "__main__":
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    M = list(map(int, input().split()))
    sumA = sum(A)
    all_sum = set()
    for i in range((n+1)//2):
        com = set(itertools.combinations(A, i))
        com_sum = set(map(sum, com))
        com_sum_rev = set(map(rev, com_sum))
        all_sum = all_sum.union(com_sum)
        all_sum = all_sum.union(com_sum_rev)
    for m in M:
        if m in all_sum:
            print("yes")
        else:
            print("no")

Submission status: Wrong Answer

Solution code:
def search(n, A, q, m):
    for M in m:
        judge = "no"
        for i in range(n-1):
            if judge == "yes":
                break
            j = i + 1
            for j in range(j, n):
                if M == A[i] + A[j]:
                    judge = "yes"
                    break
        if judge == "yes":
            print("yes")
        else:
            print("no")

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

Submission status: Wrong Answer

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

RES = []
for i in range(0, n-1):
      for j in range(i+1, n):
            t = int(A[i]) + int(A[j])
            RES.append(t)
#print(RES)

for i in range(0, q):
      for j in range(0, len(RES)):
            #print("M[i]=== {}".format(M[i]))
            #print("RES[j]=== {}".format(RES[j]))
            if int(M[i]) == RES[j]:
                  print("yes")
                  break
            else:
                  j = j+1
      if j == len(RES):
            print("no")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2000000)

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

check = True

def exh_search(n, l):
	global check
	if check:
		if(n == 0):
			check = False
		else:
			if len(l) > 1:
				exh_search(n, l[1:])
				if n >= l[0]:
					exh_search(n - l[0], l[1:])

for x in m:
	check = True
	exh_search(x, a)
	if check:
		print('no')
	else:
		print('yes')

Submission status: Wrong Answer

Solution code:
import sys
import time
sys.setrecursionlimit(2000000)

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

check = True
a.sort(reverse = True)

def exh_search(n, l):
	global check
	if check:
		if(n == 0):
			check = False
		else:
			if len(l) > 0:
				exh_search(n, l[1:])
				if n >= l[0]:
					exh_search(n - l[0], l[1:])

start = time.time()

for x in m:
	check = True
	exh_search(x, a)
	if check:
		print('no')
	else:
		print('yes')
		
print(time.time() - start)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
????????????
?????? n ?????°??? A ??¨??´??° m ???????????????A ???????´?????????????????????????????´?????¶????????????????
m ???????????????????????????????????????????????°????????????????????????????????????
AA ??????????´???????????????????????????¨?????§????????????

??°??? A ??????????????????????????§???????????¨?????? q ?????? mi ????????????????????§???
???????????????????????? "yes" ????????? "no" ??¨???????????????????????????

n ??? 20 ; q ??? 200 ; 1 ??? A???????´? ??? 2000 ; 1 ??? Mi ??? 2000

"""
def kenzan(m, n, A):

    if m < A[0]:
        return -1
    elif m == A[0]:
        return 0

    # ?????????????????§????????°???????????£????????????
    total = 0
    nA = [A[0]]
    for i in range(1,n):
        if A[i] == m:
            return 0
        elif A[i] + A[0] > m:
            break
        nA.append(A[i])
        total += A[i]
#    print("{} total:{}".format(nA,total))

    if m > total:
        return -1

    n =len(nA)
    l = 2 ** n
    for i in range(1,l):
        c = 0
        bi = "{0:0<{width}b}".format(i,width=n)
        bi = bi[::-1]
#        print("{0:2}[{1}] m[{2:4}] {3}".format(i, bi,m, n))
        for j in range(n):
#            print("\tj:{} bi:{} Aj[{:4}]".format(j, bi[j], A[j]))
            if bi[j] == "1":
                x = c + nA[j]
#                print("\tm[{:4}] c+Aj[{:4}] c[{:4}] j:{} Aj[{:4}]".format(m, x, c, j, A[j]))
                if x == m:
                    return 0
                elif x > m:
                    break
                else:
                    c = x
    return -1
 
def main():
    """ ????????? """
    n = int(input())
    A = sorted(map(int,input().split()))
    q = int(input())
    M = list(map(int,input().split()))

    for i in range(q):

        if kenzan(M[i], n, A) == 0:
            print("yes")
        else:
            print("no")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
????????????
?????? n ?????°??? A ??¨??´??° m ???????????????A ???????´?????????????????????????????´?????¶????????????????
m ???????????????????????????????????????????????°????????????????????????????????????
AA ??????????´???????????????????????????¨?????§????????????

??°??? A ??????????????????????????§???????????¨?????? q ?????? mi ????????????????????§???
???????????????????????? "yes" ????????? "no" ??¨???????????????????????????

n ??? 20 ; q ??? 200 ; 1 ??? A???????´? ??? 2000 ; 1 ??? Mi ??? 2000

"""
def kenzan(m, n, A):

    if m < A[0]:
        return -1
    elif m == A[0]:
        return 0

    # ?????????????????§????????°???????????£????????????
    total = A[0]
    nA = [A[0]]
    for i in range(1,n):
        if A[i] == m:
            return 0
        x = A[i] + A[0]
#        print("{} m:{} x:{} total:{}".format(nA,m, x,total))
        if x > m:
            break
        nA.append(A[i])
        total += A[i]

    if m > total:
        return -1

    n =len(nA)
    l = 2 ** n
    for i in range(1,l):
        c = 0
        bi = "{0:0<{width}b}".format(i,width=n)
        bi = bi[::-1]
#        print("{0:2}[{1}] m[{2:4}] {3}".format(i, bi,m, n))
        for j in range(n):
#            print("\tj:{} bi:{} Aj[{:4}]".format(j, bi[j], A[j]))
            if bi[j] == "1":
                x = c + nA[j]
#                print("\tm[{:4}] c+Aj[{:4}] c[{:4}] j:{} Aj[{:4}]".format(m, x, c, j, A[j]))
                if x == m:
                    return 0
                elif x > m:
#                    print("BAD")
                    break
                else:
                    c = x
    return -1
 
def main():
    """ ????????? """
    n = int(input())
    A = sorted(map(int,input().split()))
    q = int(input())
    M = list(map(int,input().split()))

    for i in range(q):

        if kenzan(M[i], n, A) == 0:
            print("yes")
        else:
            print("no")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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
    if i>=n:
        return False
    
    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:
n = int(input())
A = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))

sum_list = []
for i in range(n**2):
    b = '{0:0{1}b}'.format(i, n)
    temp = []
    for j in range(n):
        if b[j] == '1':
            temp.append(A[j])
    sum_list.append(sum(temp))


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

Submission status: Wrong Answer

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

sum_list = []
for i in range(n**2):
    b = '{0:0{1}b}'.format(i, n)

    temp = []
    for j in range(n):
        if b[j] == '1':
            temp.append(A[j])
    sum_list.append(sum(temp))

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

Submission status: Wrong Answer

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

sum_list = []
for i in range(n**2):
    b = '{0:0{1}b}'.format(i, n)
    temp = []
    for j in range(n):
        if b[j] == '1':
            temp.append(A[j])
    sum_list.append(sum(temp))

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

Submission status: Wrong Answer

Solution code:
def abc(a,b,c):
    if a==n:
        pass
    else:
        if b == 1:
            c += A[a]
            s.add(c)
        abc(a+1,0,c)
        abc(a+1,1,c)

n = int(input())
A = [int(a) for a in input().split()]
q = int(input())
M = [int(m) for m in input().split()]
s = set()

abc(0,0,0)
abc(0,1,0)

for m in M:
    if m in s:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
cpList = []

def canProd(i,m,a,n):
    if m in cpList:
        return True

    if m == 0:
        return True
    if i >= n:
        return False

    res = canProd(i+1,m,a,n) or canProd(i+1,m-a[i],a,n)
    return res


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

for i in m:
    if canProd(0,i,a,n):
        print("yes")
        cpList.append(i)
    else:
        print("no")

Submission status: Wrong Answer

Solution code:
def check(A, n,  mi):
    i, E, s = 0, [0 for i in range(n)], 0
    while i < n:
        if s == mi: return True
        if E[i] == 0:
            s += A[i]
            E[i] = 1
            i = 0
        else:
            E[i] = 0
            s -= A[i]
            i += 1
    return False

def ALDS1_5A():
    n, A, q = int(input()),list(map(int, input().split())), int(input())
    for m in input().split():
        if check(A, n, int(m)):
            print('Yes')
        else:
            print('no')

if __name__ == '__main__':
    ALDS1_5A()

Submission status: Wrong Answer

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

add_result = [0]*2001
for i in a:
	for j in range(len(add_result)):
		if add_result[j] == 1:
			try:
				add_result[i+j] = 1	
			except:
				pass
	add_result[i] = 1

for target in m:
	if add_result[target] == 1:
		print("yes")
	else:
		print("no")

Submission status: Wrong Answer

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

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 j in range(q):
    if solve(0, j):
        print("yes")
    else:
        print("no")

Submission status: Wrong Answer

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

table = [[0 for i in range(max(M)+1)] for j in range(n)]

def solve(i, m):

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

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

Submission status: Wrong Answer

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

table = [[0 for i in range(max(M)+1)] for j in range(n)]

def solve(i, m):

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

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

Submission status: Wrong Answer

Solution code:
from itertools import product


def main():
    """
    2^20 = 1,048,576
    q = 200
    200,000,000
    limit 5s ???????????????OK
    """
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    M = map(int, input().split())

    dp(n, A, q, M)


def combination(n, A, q, M):
    for m in M:
        if m == 0 or solve(m, A, n):
            print("yes")
        else:
            print("no")


def dp(n, A, q, M):
    M_max = 2000
    _dp = [False] * (M_max + 1)
    for a in A:
        for i in range(1, M_max + 1):
            if _dp[i] and i + a <= M_max:
                _dp[i + a] = True
        # ???????¨????????????¨????????°?????¨????¨±????????????????????¨??§
        _dp[a] = True

    for m in M:
        if _dp[m]:
            print("yes")
        else:
            print("no")


def solve(m, A, n):
    # for b in f1(n):
    for b in product([0, 1], repeat=n):
        s = sum(a * bit for a, bit in zip(A, b))
        if m == s:
            return True

    return False


def f1(n):
    for i in range(2 ** n):
        # 0/1???n??????????????????bit????????¨
        # 0b ?????????
        bit = bin(i)[2:]
        yield map(int, bit.zfill(n))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

def main():
    base = get_input()
    li = get_input()
    base.sort()

    for l in li:
        print(check_list(base, l))


def check_list(base, n):
    for idx, val in enumerate(base):
        if val > n:
            break
        elif val == n:
            return 'yes'
        else:
            if n - val in base[:idx]:
                return 'yes'

    return 'no'


def get_input():
    _ = int(input())
    li = [int(x) for x in input().split(' ')]
    return li


main()

Submission status: Wrong Answer

Solution code:

def main():
    base = get_input()
    li = get_input()
    base.sort()

    for l in li:
        print(check_list(base, l))


def check_list(base, n):
    for idx, val in enumerate(base):
        if val > n:
            break
        elif val == n:
            return 'yes'
        else:
            if n - val in base[:idx]:
                return 'yes'
            else:
                check_list(base[:idx], n - val)

    return 'no'


def get_input():
    _ = int(input())
    li = [int(x) for x in input().split(' ')]
    return li


main()

Submission status: Wrong Answer

Solution code:
class Tree:
    class Node:
        def __init__(self, n):
            self.left = None
            self.right = None
            self.n = n

        def find(self, total):
            if total < self.n:
                return (self.right is not None
                        and self.right.find(total))
            elif total == self.n:
                return True
            else:
                return (self.left is not None
                        and self.left.find(total-self.n))

        def __str__(self):
            cs = []
            if self.left is not None:
                cs.append(str(self.left))
            if self.right is not None:
                cs.append(str(self.right))

            return "{} -> ({})".format(self.n, ",".join(cs))


    def __init__(self, ns):
        self.top = self.Node(0)
        self.build_node(self.top, sorted(ns))

    def has_subset(self, total):
        return self.top.find(total)

    def build_node(self, node, ns):
        if len(ns) == 0:
            return
        
        node.left = self.Node(ns[-1])
        node.right = self.Node(ns[-1])
        self.build_node(node.left, ns[:-1])
        self.build_node(node.right, ns[:-1])


def run():
    _ = int(input())  # flake8: noqa
    ns = [int(i) for i in input().split()]

    tree = Tree(ns)
    _ = int(input())  # flake8: noqa
    
    for q in (int(j) for j in input().split()):
        if tree.has_subset(q):
            print("yes")
        else:
            print("no")


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

Solution code:
def create_sums(ns):
    if len(ns) == 0:
        return set()

    s = create_sums(ns[1:])
    return {e + ns[0] for e in s} | s | {ns[0]}


def run_set():
    _ = int(input())  # flake8: noqa
    ns = [int(i) for i in input().split()]

    sums = create_sums(ns)
    _ = int(input())  # flake8: noqa
    
    for q in (int(j) for j in input().split()):
        if q in sums:
            print("yes")
        else:
            print("no")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed May  2 21:28:06 2018
ALDS1_5a
@author: maezawa
"""
import itertools as itr

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

for i in m:
    yesorno = False
    b = []
    for j in a:
        if j < i:
            b.append(j)
    #print(b)
    if len(b)>2:
        for r in range(2, len(b)+1):
            for comb in itr.combinations(b,r):
                #print(i,comb)
                if sum(comb) == i:
                    yesorno = True
                    break
            if yesorno:
                break
    if yesorno:
        print('yes')
    else:
        print('no')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed May  2 21:28:06 2018
ALDS1_5a
@author: maezawa
"""
import itertools as itr

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

for i in m:
    yesorno = False
    b = []
    for j in a:
        if j < i:
            b.append(j)
    #print(b)
    if len(b)>=2:
        for r in range(2, len(b)+1):
            for comb in itr.combinations(b,r):
                #print(i,comb)
                if sum(comb) == i:
                    yesorno = True
                    break
            if yesorno:
                break
    if yesorno:
        print('yes')
    else:
        print('no')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed May  2 21:28:06 2018
ALDS1_5a
@author: maezawa
"""
import itertools as itr

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

sum_array = []
for r in range(1,n+1):
    for comb in itr.combinations(a, r):
        sum_array.append(sum(comb))

for i in m:
    yesorno = 'no'
    for j in sum_array:
        if i == j:
            yesorno == 'yes'
            break
    print('yes')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed May  2 21:28:06 2018
ALDS1_5a
@author: maezawa
"""
import itertools as itr

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

sum_array = []
for r in range(1,n+1):
    for comb in itr.combinations(a, r):
        sum_array.append(sum(comb))

for i in m:
    yesorno = 'no'
    for j in sum_array:
        print(i, j)
        if i == j:
            yesorno = 'yes'
            break
    print(yesorno)

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