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:
def solve(i, j):
    if i == 0:
    	return True
    if j < n and A[0] <= i <= sum(A[j:]):
        x = solve(i-A[j], j+1)
        if x:
        	return x
        y = solve(i, j+1)
        if y:
        	return y

n = input()
A = map(int, raw_input().split())
p = input()
m = map(int, raw_input().split())

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

Submission status: Wrong Answer

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

min = min(A)
sum = sum(A)

def solve(i,m):
  if sum < m or min > m:
    return False
  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 = input()
A = map(int, raw_input().split())
q = input()
M = map(int, raw_input().split())

min = min(A)
sum = sum(A)

def solve(i,m):
  if sum < m or min < m:
    return False
  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:
class ExhaustiveSearch:
    def solve(self, n, a, q, m):
        for mm in m:
            if self.es(0, mm):
                print("yes")
            else:
                print("no")
    def es(self, i, m): 
        if m == 0:
            return True
        if i >= n:
            return False
        res = self.es(i + 1, m) or self.es(i + 1, m - a[i])
        return res

if '__name__' == '__main__':
    n = int(input())
    a = [int(i) for i in input().rstrip().split(" ")]
    q = int(input())
    m = [int(i) for i in input().rstrip().split(" ")]
    x = ExhaustiveSearch()
    x.solve(n, a, q, m)

Submission status: Wrong Answer

Solution code:
import sys

def exhaustiveSearch(A, m):
    if len(A) == 0 or A[0] > m:
        return False
    elif A[0] == m:
        return True
    return exhaustiveSearch(A[1:], m) or exhaustiveSearch(A[1:], m - A[0])

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    A = map(int, lines[1].split())
    M = map(int, lines[3].split())

    for m in M:
        if exhaustiveSearch(A, m):
            print "yes"
        else:
            print "no"

Submission status: Wrong Answer

Solution code:
import sys

def exhaustiveSearch(A, m):
    if len(A) == 1 and A[0] != m or A[0] > m:
        return False
    elif A[0] == m:
        return True
    return exhaustiveSearch(A[1:], m) or exhaustiveSearch(A[1:], m - A[0])

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    A = map(int, lines[1].split())
    M = map(int, lines[3].split())

    for m in M:
        if exhaustiveSearch(A, m):
            print "yes"
        else:
            print "no"

Submission status: Wrong Answer

Solution code:
'''
Created on 2016/03/18

@author: toshi
'''

#n = map(int, raw_input())
n = int(raw_input())
A = map(int, raw_input().split())
#q = map(int, raw_input())
q = int(raw_input())
m = map(int, raw_input().split())

A = sorted(A)

def sum_A(A, n, pos, sum, m, flg):
    if flg[0] == "yes":
        return 0
    if sum == m:
        flg[0] = "yes"
        return 0
    if pos + 1 > n - 1:
        return 0
    sum_A(A, n, pos + 1, sum + A[pos], m, flg)
    sum_A(A, n, pos + 1, sum, m, flg)

for i, m_i in enumerate(m):
    sum = 0
    flg = ["no"]
    sum_A(A, n, 0, sum, m_i, flg)
    print flg[0]

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

A = sorted(A)

def sum_A(A, n, pos, sum, m, flg):
    if flg[0] == "yes":
        return 0
    if sum == m:
        flg[0] = "yes"
        return 0
    if pos + 1 > n - 1:
        return 0
    sum_A(A, n, pos + 1, sum + A[pos], m, flg)
    sum_A(A, n, pos + 1, sum, m, flg)

for i, m_i in enumerate(m):
    sum = 0
    flg = ["no"]
    sum_A(A, n, 0, sum, m_i, flg)
    print flg[0]

Submission status: Wrong Answer

Solution code:
'''
Created on 2016/03/18

@author: toshi
'''

#n = map(int, raw_input())
n = int(raw_input())
A = map(int, raw_input().split())
#q = map(int, raw_input())
q = int(raw_input())
m = map(int, raw_input().split())

A = sorted(A)

def sum_A(A, n, pos, sum, m, res):
    if res[0] == "yes":
        return 0
    if sum == m:
        res[0] = "yes"
        return 0
    if pos + 1 > n - 1:
        return 0
    sum_A(A, n, pos + 1, sum + A[pos], m, res)
    sum_A(A, n, pos + 1, sum, m, res)

for i, m_i in enumerate(m):
    sum = 0
    res = ["no"]
    sum_A(A, n, 0, sum, m_i, res)
    print res[0]

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

A = sorted(A)

def sum_A(A, n, pos, sum, m, res):
    if res[0] == "yes":
        return 0
    if sum == m:
        res[0] = "yes"
        return 0
    if pos + 1 > n - 1:
        return 0
    sum_A(A, n, pos + 1, sum + A[pos], m, res)
    sum_A(A, n, pos + 1, sum, m, res)

for i, m_i in enumerate(m):
    sum = 0
    res = ["no"]
    sum_A(A, n, 0, sum, m_i, res)
    print res[0]

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

A = sorted(A)
m = sorted(m)

def sum_A(A, n, pos, sum, m, res):
    if res[0] == "yes":
        return 0
    if sum < A[pos]:
        return 0
    if sum + A[pos] == m:
        res[0] = "yes"
        return 0
    if pos + 1 > n - 1:
        return 0
    sum_A(A, n, pos + 1, sum + A[pos], m, res)
    sum_A(A, n, pos + 1, sum, m, res)

for i, m_i in enumerate(m):
    sum = 0
    res = ["no"]
    sum_A(A, n, 0, sum, m_i, res)
    print res[0]

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

A = sorted(A)
m = sorted(m)

def sum_A(A, n, pos, sum, m, res):
    if res[0] == "yes":
        return 0
    if sum + A[pos] == m:
        res[0] = "yes"
        return 0
    if sum + A[pos] > m:
        return 0
    if pos + 1 > n - 1:
        return 0
    sum_A(A, n, pos + 1, sum + A[pos], m, res)
    sum_A(A, n, pos + 1, sum, m, res)

for i, m_i in enumerate(m):
    sum = 0
    res = ["no"]
    sum_A(A, n, 0, sum, m_i, res)
    print res[0]

Submission status: Wrong Answer

Solution code:
import time

def sum_A(A, n):
    dic = {}
    #A_ = A
    #n_ = n
    
    def solve(i, m):
        if (i, m) in dic:
            return dic[(i, m)]
        if m == 0:
            dic[(i, m)] = True
        elif i >= n:
            dic[(i, m)] = False
        elif solve(i+1, m):
            dic[(i, m)] = True
        elif solve(i+1, m-A[i]):
            dic[(i, m)] = True
        else:
            dic[(i, m)] = False
        return dic[(i, m)]
    
    return solve

if __name__ == '__main__':
    n = int(raw_input())
    A = map(int, raw_input().split())
    q = int(raw_input())
    m = map(int, raw_input().split())

    #A = sorted(A)
    start = time.time()
    solve = sum_A(A, n)
    for m_i in m:
        print "yes" if solve(0, m_i) else "no"
    end = time.time()
    print end - start

Submission status: Wrong Answer

Solution code:
import time

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

if __name__ == '__main__':
    n = int(raw_input())
    A = map(int, raw_input().split())
    q = int(raw_input())
    m = map(int, raw_input().split())

    start = time.time()
    for m_i in m:
        print "yes" if solve(0, m_i) else "no"
    end = time.time()
    print end - start

Submission status: Wrong Answer

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

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

for num in m:
    solve(0, num)

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(j, i):
    '''A[j]?????§?????¨??????i???M?????????????´??????????A[0],..,A[j]??????????????????????????????
    '''
    if i == 0:
        return True
    if j > n - 1:
        return False

    if i >= A[j]:
        tmp1 = solve(j + 1, i - A[j])
        tmp2 = solve(j + 1, i)
    else:
        # A[j]???????????§???????????§????????????????????????j??????????????\?????????
        return False

    if tmp1 or tmp2:
        return True
    else:
        return False


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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf_8 -*-

from itertools import repeat

def rec(s, i, total, m):
    if total == m:
        return 1

    if len(s) - 1 == i or total > m:
        return 0

    return rec(s, i + 1, total, m) + rec(s, i + 1, total + s[i], m)

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf_8 -*-

from itertools import repeat

def rec(s, i, total, m):
    if total == m:
        return 1

    if len(s) == i or total > m:
        return 0

    return 1 if rec(a, 0, 0, i) > 0 else rec(s, i + 1, total + s[i], m)

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

Submission status: Wrong Answer

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

q = int(raw_input())
mi = map(int, raw_input().split())

def f(m, A):
    a = list(A)
    if len(a) == 0:
        return False
    i = 0
    while True:
        while (i < len(a)) and (a[i] <= m): i+=1
        m -= a[i-1]
        a.pop(i-1)
        if   m == 0:
            return True
        elif m > 0:
            return f(m, a)
        else:
            return False

for m in mi:
    if f(m, A):
        print "yes"
    else:
        print "no"

Submission status: Wrong Answer

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

q = int(raw_input())
mi = map(int, raw_input().split())

def f(m, A):
    a = list(A)
    if len(a) == 0:
        return False
    i = 0
    while True:
        while (i < len(a)) and (a[i] <= m): i+=1
        m -= a[i-1]
        a.pop(i-1)
        if   m == 0:
            return True
        elif m > 0:
            return f(m, a)
        else:
            return False

for m in mi:
    if f(m, A):
        print "yes"
    else:
        print "no"

Submission status: Wrong Answer

Solution code:
n1 = int(input())
A = list(map(int, input().split()))
n2 = int(input())
q = list(map(int, input().split()))

B = []

n = n1
ans = list("no" for i in range(n2))

for i in range(2 ** n):
    B = list(map(int, format(i, "b").zfill(n)))[::-1]
    C = sum([ x*y for x, y in zip(A, B)])
    for i, r in enumerate(q):
        if  C == r:
            ans[i] = "yes"
            break
print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
n1 = int(input())
A = list(map(int, input().split()))
n2 = int(input())
q = list(map(int, input().split()))

B = []

n = n1
ans = list("no" for i in range(n2))

for i in range(2 ** n):
    C0 = []
    B = list(map(int, format(i, "b").zfill(n)))[::-1]
    C0 = [ x*y for x, y in zip(A, B)]
    C = sum(C0)
#    print(C0, C)
    for j, r in enumerate(q):
        if  C == r:
            ans[j] = "yes"
            break
print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
import itertools as it

def check(p, li):
    li_ad = [i for i in li if i < p]
    flag = False
    for j in range(len(li_ad)):
        li_perm = list(it.permutations(li_ad, j+1))
        for k in range(len(li_perm)):
            if sum(li_perm[k]) == p:
                flag = True
                break
        if flag:
            break
        
    return flag
    
    
n = int(input())
A = sorted(list(map(int, input().split())))
q = int(input())
m = list(map(int, input().split()))

min_range = A[0] + A[1]
max_range = sum(A)

for i in range(q):
    if m[i] < min_range or m[i] > max_range:
        print('no')
    else:
        print('yes' if check(m[i], A) else 'no' )

Submission status: Wrong Answer

Solution code:
import itertools as it

def check(p, li):
    li_ad = [i for i in li if i <= p]
    flag = False
    for j in range(len(li_ad)):
        li_perm = list(it.permutations(li_ad, j+1))
        for k in range(len(li_perm)):
            if sum(li_perm[k]) == p:
                flag = True
                break
        if flag:
            break
        
    return flag
    
    
n = int(input())
A = sorted(list(map(int, input().split())))
q = int(input())
m = list(map(int, input().split()))

min_range = A[0] + A[1]
max_range = sum(A)

for i in range(q):
    if m[i] < min_range or m[i] > max_range:
        print('no')
    else:
        print('yes' if check(m[i], A) else 'no' )

Submission status: Wrong Answer

Solution code:
from sets import Set

input()
n_list=map(int, raw_input().split())
input()
m_list=map(int, raw_input().split())

n = len(n_list)

pool = Set([])

dic ={}

def func(idx, m):

    if m in dic.keys():
        return dic[m]

    if m==0:
        # print "hit"
        return True
    elif idx >= n:
        # print "over"
        return False
    elif  func(idx + 1, m):
        dic[m]=True
    
    elif func(idx + 1, m - n_list[idx]):
        dic[m]=True
    else:
        dic[m]=False
 
    return dic[m]

for v in m_list:

    #print dic
    print "yes" if func(0, v) else "no"

Submission status: Wrong Answer

Solution code:
input()
nlist=map(int, raw_input().split())
input()
qlist=map(int, raw_input().split())

n = len(nlist)

dic={}

def func(idx, m):
    
    try:
        if dic[m][0] <= idx:
            return dic[m][1]
    except:
        pass

    if m==0:
        return True
    elif idx > n-1:
        return False
    elif func(idx+1, m):
        dic[m] = [idx, True]
        return True
    elif func(idx+1, m-nlist[idx]):
        dic[m] = [idx, True]
        return True

    dic[m] = [idx, False]
    return False


for q in qlist:
    print "yes" if func(0, q) else "no"

Submission status: Wrong Answer

Solution code:
# encoding: utf-8


import sys

__input = sys.stdin.readlines()
length_1 = int(__input[0])
array_1 = list(map(int, __input[1].split()))
length_2 = int(__input[2])
array_2 = list(map(int, __input[3].split()))


def solution():
    print(length_1, array_1, length_2, array_2)
    assert length_1 == len(array_1) and length_2 == len(array_2)

    for i in range(length_2):
        ans = solve(0, array_2[i])
        if ans:
            print("yes")
        else:
            print("no")
    return None


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


if __name__ == '__main__':
    solution()

Submission status: Wrong Answer

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=jp

def exhaustive_search(target_list,m):

    for i in range(len(target_list)):
        result = m - target_list[i]
        if result == 0:
            return True
        elif result < 0:
            return False
        elif result > 0:
            if exhaustive_search(target_list[i+1:], result):
                return True
                
    return False

def main():
    n_input = int(input())
    input_data = [int(a) for a in input().split()]
    n_target = int(input())
    target_list = [int(a) for a in input().split()]

    for m in target_list:
        if exhaustive_search(input_data,m):
            print("yes")
        else:
            print("no")
            
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=jp
def solve(input_data, target_num):
    for i in range(len(input_data)):
        #print("begin")
        if exhaustive_search(input_data, i, target_num):
            return True
    return False

def exhaustive_search(input_list, input_index, target_num):
    #print(target_num, input_list[input_index])
    if input_index >= len(input_list):
        return False
    if target_num == input_list[input_index]:
        return True
    elif target_num <= input_list[input_index]:
        return False
    return exhaustive_search(input_list, input_index + 1, target_num - input_list[input_index]) or exhaustive_search(input_list, input_index + 1, target_num)
 
def main():
    n_input = int(input())
    input_data = [int(a) for a in input().split()]
    n_target = int(input())
    target_list = [int(a) for a in input().split()]

    for m in target_list:
        if solve(input_data, m):
            print("yes")
        else:
            print("no")
            
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

"""
from itertools import combinations

if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    M = [int(x) for x in input().split(' ')]
    pick = int(input())
    A = [int(x) for x in input().split(' ')]
    #A = [1, 5, 7, 10, 21]
    #pick = 4
    #M = [2, 4, 17, 8]

    # ????????????
    results = ['no' for x in range(len(M))]

    for p in range(1, pick+1):
        combi = combinations(A, p)
        for choice in combi:
            total = sum(choice)
            if total in M:
                i = M.index(total)
                results[i] = 'yes'

    # ???????????????
    for txt in results:
        print(txt)

Submission status: Wrong Answer

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

"""
from itertools import combinations

if __name__ == '__main__':
    # ??????????????\???
    num1 = int(input())
    M = [int(x) for x in input().split(' ')]
    num2 = int(input())
    A = [int(x) for x in input().split(' ')]
    #A = [1, 5, 7, 10, 21]
    #pick = 4
    #M = [2, 4, 17, 8]

    # ????????????
    results = ['no' for x in range(len(A))]

    for p in range(1, len(M)+1):
        combi = combinations(M, p)
        for choice in combi:
            total = sum(choice)
            if total in A:
                i = A.index(total)
                results[i] = 'yes'

    # ???????????????
    for txt in results:
        print(txt)

Submission status: Wrong Answer

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

def dfs(sum,target,index):
    if sum==target:
        return True

    if index==n:
        return False

    if target<sum:
        return False

    if dfs(sum+a[index],target,index+1):
        return True

    if dfs(sum,target,index+1):
        return True

    return False

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

Submission status: Wrong Answer

Solution code:
def solve(p, t):
  if p >= len(A): return False
  if t == A[p]: return True
  if t <= 0: return True
  #print("({}, {})".format(p, t))

  if solve(p + 1, t):
    return True
  else:
    return solve(p + 1, t - A[p])

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

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

Submission status: Wrong Answer

Solution code:
class Solver():
    def __init__(self, A: [int]):
        self.A = A
        self.max_depth = len(A)

    def solve(self, tgt):
        self.tgt = tgt
        return self._rec_solve(0, 0)

    def _rec_solve(self, _sum, index):
        if index >= self.max_depth or _sum > self.tgt:
            return False
        elif _sum == self.tgt:
            return True
        else:
            return self._rec_solve(_sum + self.A[index], index + 1) or self._rec_solve(_sum, index + 1)
            


if __name__ == '__main__':
    n = int(input())
    A = [int(i) for i in input().rstrip().split()]
    print(A)
    q = int(input())
    m_ary = [int(i) for i in input().rstrip().split()]
    print(m_ary)
    s = Solver(A)
    for i in m_ary:
        print(s.solve(i))

Submission status: Wrong Answer

Solution code:
class Solver():
    def __init__(self, A: [int]):
        self.A = A
        self.max_depth = len(A)

    def solve(self, tgt):
        self.tgt = tgt
        if self._rec_solve(0, 0):
            return 'yes'
        else:
            return 'no'

    def _rec_solve(self, _sum, index):
        if index >= self.max_depth or _sum > self.tgt:
            return False
        elif _sum == self.tgt:
            return True
        else:
            return self._rec_solve(_sum + self.A[index], index + 1) or self._rec_solve(_sum, index + 1)
            


if __name__ == '__main__':
    n = int(input())
    A = [int(i) for i in input().rstrip().split()]
    print(A)
    q = int(input())
    m_ary = [int(i) for i in input().rstrip().split()]
    print(m_ary)
    s = Solver(A)
    for i in m_ary[:-1]:
        print(s.solve(i))
    print(m_ary[-1], end='')

Submission status: Wrong Answer

Solution code:
class Solver():
    def __init__(self, A: [int]):
        self.A = A
        self.max_depth = len(A)

    def solve(self, tgt):
        self.tgt = tgt
        if self._rec_solve(0, 0):
            return 'yes'
        else:
            return 'no'

    def _rec_solve(self, _sum, index):
        if index >= self.max_depth or _sum > self.tgt:
            return False
        elif _sum == self.tgt:
            return True
        else:
            return self._rec_solve(_sum + self.A[index], index + 1) or self._rec_solve(_sum, index + 1)
            


if __name__ == '__main__':
    n = int(input())
    A = [int(i) for i in input().rstrip().split()]
    q = int(input())
    m_ary = [int(i) for i in input().rstrip().split()]
    s = Solver(A)
    for i in m_ary[:-1]:
        print(s.solve(i))
    print(m_ary[-1], end='')

Submission status: Wrong Answer

Solution code:
class Solver():
    def __init__(self, A: [int]):
        self.A = A
        self.max_depth = len(A)

    def solve(self, tgt):
        self.tgt = tgt
        if self._rec_solve(0, 0):
            return 'yes'
        else:
            return 'no'

    def _rec_solve(self, _sum, index):
        if index >= self.max_depth or _sum > self.tgt:
            return False
        elif _sum == self.tgt:
            return True
        else:
            return self._rec_solve(_sum + self.A[index], index + 1) or self._rec_solve(_sum, index + 1)
            


if __name__ == '__main__':
    n = int(input())
    A = [int(i) for i in input().rstrip().split()]
    q = int(input())
    m_ary = [int(i) for i in input().rstrip().split()]
    s = Solver(A)
    for i in m_ary[:-1]:
        print(s.solve(i))
    print(s.solve(m_ary[-1]), end='')

Submission status: Wrong Answer

Solution code:
class Solver():
    def __init__(self, A: [int]):
        self.A = A
        self.max_depth = len(A)

    def solve(self, tgt):
        self.tgt = tgt
        self.history = (len(self.A)+1)*[4000 * [None]]
        if self._rec_solve(0, 0):
            return 'yes'
        else:
            return 'no'

    def _rec_solve(self, _sum, index):
        if self.history[index][_sum] is not None:
            return self.history[index][_sum]
        elif _sum == self.tgt:
            return True
        elif index >= self.max_depth or _sum > self.tgt:
            return False
        else:
            self.history[index][_sum] = self._rec_solve(_sum + self.A[index], index + 1) or self._rec_solve(_sum, index + 1)
            return self.history[index][_sum]
            


if __name__ == '__main__':
    n = int(input())
    A = [int(i) for i in input().rstrip().split()]
    q = int(input())
    m_ary = [int(i) for i in input().rstrip().split()]
    s = Solver(A)
    for i in m_ary[:]:
        print(s.solve(i))

Submission status: Wrong Answer

Solution code:
class Solver():
    def __init__(self, A: [int]):
        self.A = A
        self.max_depth = len(A)

    def solve(self, tgt):
        self.tgt = tgt
        self.history = (len(self.A)+1)*[4000 * [None]]
        if self._rec_solve(0, 0):
            return 'yes'
        else:
            return 'no'

    def _rec_solve(self, _sum, index):
        if _sum == self.tgt:
            return True
        elif self.history[index][_sum] is not None:
            return self.history[index][_sum]
        elif index >= self.max_depth or _sum > self.tgt:
            return False
        else:
            self.history[index][_sum] = self._rec_solve(_sum + self.A[index], index + 1) or self._rec_solve(_sum, index + 1)
            return self.history[index][_sum]
            


if __name__ == '__main__':
    n = int(input())
    A = [int(i) for i in input().rstrip().split()]
    q = int(input())
    m_ary = [int(i) for i in input().rstrip().split()]
    s = Solver(A)
    for i in m_ary[:]:
        print(s.solve(i))

Submission status: Wrong Answer

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

n2 = n**2
aa = [0 for _ in range(n2)]
for i in range(n):
    t = 2**i
    for j in range(n2):
        if (j//t)%2:
            aa[j] += a[i]
aa = set(aa)

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

Submission status: Wrong Answer

Solution code:
memo = {}
def solve(p, t):
  key = "{}:{}".format(p, t)
  if key in memo: return memo[key]
  if p >= len(A): return False
  if t == A[p]: return True
  if t <= 0: return False
  #print("({}, {})".format(p, t))

  if solve(p + 1, t):
    memo[key] = True
    return True
  else:
    memo[key] = False
    return solve(p + 1, t - A[p])

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

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

Submission status: Wrong Answer

Solution code:
n = input()

Submission status: Wrong Answer

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

def execute(m):
    for a1 in A:
        for a2 in A:
            if int(a1) != int(a2) and int(a1) + int(a2) == int(m):
                print('yes')
                return
    print('no')
    return

for m in M:
    execute(m)

Submission status: Wrong Answer

Solution code:
count = 0
def merge(A,left,mid,right):
    n1 = mid- left
    n2 = right - mid
    L = [0 for i in range(n1+1)]
    R = [0 for i in range(n2+1)]

    for i in range(n1):
        L[i]= A[left+i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1] = float("INFINITY")
    R[n2] = float("INFINITY")
    i = 0
    j = 0
    for k in range(left,right):
        global count 
        count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j += 1
            
def mergeSort(A,left,right):
    if left + 1 < right:
        mid = (left+ right) //2
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

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

mergeSort(A,0,n)

print(" ".join(map(str,A)))
print(count)

Submission status: Wrong Answer

Solution code:
numA = int(input().rstrip())
listA = list(map(int,input().rstrip().split(" ")))
numQ = int(input().rstrip())
listQ = list(map(int,input().rstrip().split(" ")))

sumA = []
cnt = 0

for i in range(numA):
    for j in range(i+1, numA):
         sumA.append(listA[i]+listA[j])

for i in range(numQ):
    if sumA.count(listQ[i]) > 0:
        #exsits
        print("yes")
    else:
        print("no")

Submission status: Wrong Answer

Solution code:
numA = int(input().rstrip())
listA = list(map(int,input().rstrip().split(" ")))
numQ = int(input().rstrip())
listQ = list(map(int,input().rstrip().split(" ")))

sumA = listA
cnt = 0

sumA.append(sum(listA))

for i in range(numA):
    for j in range(i+1, numA):
         sumA.append(listA[i]+listA[j])



print(sumA)
for i in range(numQ):
    if sumA.count(listQ[i]) > 0:
        #exsits
        print("yes", listQ[i])
    else:
        print("no", listQ[i])

Submission status: Wrong Answer

Solution code:
numA = int(input().rstrip())
listA = list(map(int,input().rstrip().split(" ")))
numQ = int(input().rstrip())
listQ = list(map(int,input().rstrip().split(" ")))

sumA = listA
cnt = 0

sumA.append(sum(listA))

for i in range(numA):
    for j in range(i+1, numA):
         sumA.append(listA[i]+listA[j])



#print(sumA)
for i in range(numQ):
    if sumA.count(listQ[i]) > 0:
        #exsits
        print("yes")
    else:
        print("no")

Submission status: Wrong Answer

Solution code:
import itertools
given_n = int(input())
given_A = list(map(int,input().split()))
given_q = int(input())
given_m = list(map(int,input().split()))

for mi in given_m:
    partial_A = list(filter(lambda ai:ai<mi,given_A))
    check = False
    for num in range(1,len(partial_A)+1):
        combinationPartialA = list(itertools.combinations(partial_A,num))
        for tmp_cpa in combinationPartialA:
            if sum(tmp_cpa) == mi:
                check = True
    if check:
        print("yes")
    else:
        print("no")