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 M i . 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 ( M i ) are given. Output For each question M i , print yes or no . Constraints  n ≤ 20  q ≤ 200  1 ≤ elements in A ≤ 2000  1 ≤ M i ≤ 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].

Solution (Python):
import re
from itertools import product
import itertools

q1 = int(input())
q2 = input()
q3 = int(input())
q4 = input()

S = re.split(r' ',q2)
S=list(map(int, S))

T = re.split(r' ',q4)
T=list(map(int, T))

S_len = len(S)
T_len = len(T)

array = []
for j in range(q1+1):
    x = list(itertools.combinations(S, j))
    for k in range(len(x)):
        y = sum(x[k])
        array.append(y)

for i in range(T_len):
    if(T[i] in array):
        print("yes")
    else:
        print("no")

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
memory = [[-1 for i in range(max(m)+1)]for j in range(n)]

def f(i, m):
    if m == 0:
        return 1
    elif i >= n:
        return 0
    elif memory[i][m] != -1:
        return memory[i][m]
    elif m - a[i] >= 0:
        res0 = f(i+1, m)
        res1 = f(i+1, m-a[i])
        if res0 or res1:
            memory[i][m] = 1
            return 1
        else:
            memory[i][m] = 0
            return 0
    else:
        res = f(i+1, m)
        memory[i][m] = res
        return res

for k in m:
    print('yes' if f(0, k) else 'no')

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
memory = [[-1 for i in range(max(m)+1)]for j in range(n)]

def f(i, m):
    if m == 0:
        return 1
    elif i >= n:
        return 0
    elif memory[i][m] != -1:
        return memory[i][m]
    elif m - a[i] >= 0:
        res0 = f(i+1, m)
        res1 = f(i+1, m-a[i])
        if res0 or res1:
            memory[i][m] = 1
            return 1
        else:
            memory[i][m] = 0
            return 0
    else:
        res = f(i+1, m)
        memory[i][m] = res
        return res

for k in m:
    print('yes' if f(0, k) else 'no')

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


u = set()

def agari(i):
    if X[i]==1:
        X[i]=0
        agari(i+1)
    else:
        X[i]=1

X = [0]*20
k=0
while k<(pow(2,n)-1):
    y = 0
    for l in range(n):
        y += A[l]*X[l]
    u.add(y)
    agari(0)
    k+=1

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

Solution (Python):
class Tree:
    class Node:
        def __init__(self, n, left, right):
            self.left = left
            self.right = right
            self.n = n
            if left is not None:
                lt = {t + n for t in left.totals}
            else:
                lt = set()
            if right is not None:
                rt = right.totals
            else:
                rt = set()

            self.totals = lt | rt | {n}

        def find(self, total):
            return total in self.totals

        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.build_nodes(sorted(ns))

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

    def build_nodes(self, ns):
        if len(ns) == 0:
            return None

        left = self.build_nodes(ns[:-1])
        right = self.build_nodes(ns[:-1])
        node = self.Node(ns[-1], left, right)

        return node


def run_tree():
    _ = int(input())  
    ns = [int(i) for i in input().split()]

    tree = Tree(ns)
    _ = int(input())  

    for q in (int(j) for j in input().split()):
        if tree.has_subset(q):
            print("yes")
        else:
            print("no")



if __name__ == '__main__':
    run_tree()

Solution (Python):
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())  
    ns = [int(i) for i in input().split()]

    sums = create_sums(ns)
    _ = int(input())  

    for q in (int(j) for j in input().split()):
        if q in sums:
            print("yes")
        else:
            print("no")


if __name__ == '__main__':
    run_set()

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
b = [2 ** i for i in range(n)]
c = {}
for i in range(2 ** n):
    k = 0
    k += i
    v = 0
    for j in range(n)[::-1]:
        v += k // b[j] * a[j]
        k %= b[j]
    c[v] = 0
m = int(input())
a = list(map(int,input().split()))
for i in range(m):
    try:
        c[a[i]]
        print("yes")
    except:
        print("no")

Solution (Python):

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

Solution (Python):

"""
Created on Wed May  2 21:28:06 2018
ALDS1_5a_r1  
@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))
sum_array.sort()

for i in m:
    left = 0
    right = len(sum_array)
    yesorno = 'no'
    while(left < right):
        
        mid = (left+right)//2
        if sum_array[mid] == i:
            yesorno = 'yes'
            break
        elif sum_array[mid] > i:
            right = mid
        else:
            left = mid+1
            
    print(yesorno)

Solution (Python):
from itertools import combinations

n = int(input())
a_array = [int(x) for x in input().split()]
q = int(input())
m_array = [int(x) for x in input().split()]

array = []
for j in range(n + 1):
    x = combinations(a_array, j)
    for y in x:
        array.append(sum(y))

for m in m_array:
    print("yes" if m in array else "no")

Solution (Python):
import sys
sys.setrecursionlimit(100000)  

n=int(input())
A=[int(x) for x in input().split()]
minA=min(A)
sumA=0
for i in A:
    sumA+=i
    


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


def solve(i,m):
    global n
    global A
    global minA
    global sumA
    
    if m<0 or m>sumA:
        return False
    if m==0:
        return True
    if i>=n:
        return False
    
    return solve(i+1,m) or solve(i+1,m-A[i])
    
    
for m in M:
    if m<minA or m>sumA:
        print('no')
    else:
        if solve(0,m):
            print('yes')
        else:
            print('no')

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
M_DICT = {}


def make_m(i, m):
    if (i, m) in M_DICT:
        return M_DICT[(i, m)]
    if m == 0:
        return True
    if i >= N or m < 0:
        return False

    res = make_m(i+1, m) or make_m(i+1, m-A[i])
    M_DICT[(i, m)] = res
    return res


def main():
    q = int(input())
    m_lst = list(map(int, input().split()))

    for i in range(q):
        if make_m(0, m_lst[i]):
            print("yes")
        else:
            print("no")


if __name__ == '__main__':
    main()

Solution (Python):
import itertools as it

n=int(input())
A=input().split()
q=int(input())
M=input().split()
ans=[]
cnt=0

A=list(map(int,A))
M=list(map(int,M))

for i in range(len(A)):
    Ac=list(it.combinations(A,i+1))
    for j in Ac:
        ans.append(sum(j))

for i in M:
    flag=0
    for j in ans:
        if i==j:
            print("yes")
            flag=1
            break
    if flag==0:
        print("no")

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


max_A = 0
min_A = float('inf')
for num in A:
    max_A += num
    if num < min_A:
        min_A = num

def rec(i, m):
    if m < 0:
        return False
    elif m == 0:
        return True
    if i >= n:
        return False

    rst = rec(i+1, m - A[i]) or rec(i+1, m)
    return rst

for m in M:
    if m < min_A or max_A < m:
        print('no')
    elif rec(0, m):
        print('yes')
    else:
        print('no')

Solution (Python):
import itertools as ite

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

for i in range(n):
    for j in list(ite.combinations(a,i+1)):
        x.append(sum(j))
for i in range(q):
    flag = 0
    for j in x:
        if m[i] == j:
            print("yes")
            flag = 1
            break
    if flag == 0: print("no")

Solution (Python):
import itertools as it

n=int(input())
A=input().split()
q=int(input())
M=input().split()
ans=[]
cnt=0

A=list(map(int,A))
M=list(map(int,M))

for i in range(len(A)):
    Ac=list(it.combinations(A,i+1))
    for j in Ac:
        ans.append(sum(j))

for i in M:
    flag=0
    for j in ans:
        if i==j:
            print("yes")
            flag=1
            break
    if flag==0:
        print("no")

Solution (Python):
import itertools
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])
l=[0,1]
p=[]
k=0
D=[]
for v in itertools.product(l,repeat=n):
    sum=0
    for i in range(n):
        if v[i]==1:
            sum=sum+A[i]
    D.append(sum)
    k+=1
for i in range(q):
    if B[i] in D:
        C.append("yes")
    else:
        C.append("no")
for i in range(q):
    print(C[i])

Solution (Python):
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] = max(a[i-1][j-A[i-1]]+A[i-1],a[i-1][j])
            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")

Solution (Python):
def search(l, m):
    
    dp = [[False for _ in range(m+1)] for __ in range(len(l) + 1)]
    dp[0][0]= True
    for i in range(len(l)):
        for mi in range(m + 1):
            if l[i] <= mi:
                dp[i+1][mi] = dp[i][mi - l[i]] or dp[i][mi]
            else:
                dp[i+1][mi] = dp[i][mi]
    return dp[len(l)][m]


n = int(input())
l = list(map(int, input().split()))
q = int(input())
ms = list(map(int, input().split()))

for m in ms:
    if search(l, m):
        print('yes')
    else:
        print('no')

Solution (Python):
import itertools as it
 
n=int(input())
A=input().split()
q=int(input())
M=input().split()
ans=[]
cnt=0
 
A=list(map(int,A))
M=list(map(int,M))
 
for i in range(len(A)):
    Ac=list(it.combinations(A,i+1))
    for j in Ac:
        ans.append(sum(j))
 
for i in M:
    flag=0
    for j in ans:
        if i==j:
            print("yes")
            flag=1
            break
    if flag==0:
        print("no")

Solution (Python):
import itertools as itl

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

for i in range(n):
    cmb = list(itl.combinations(A, i+1))
    for j in cmb:
        S.append(sum(j))

for m in M:
    flg = False
    for s in S:
        if s == m:
            flg = True
            break
    if flg:
        print("yes")
    else:
        print("no")

Solution (Python):
n = int(input())
a = list(map(int, input().split(' ')))
q = int(input())
M = list(map(int, input().split(' ')))
minA = min(a)
sumA = 0
for i in a:
    sumA += i


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 M:
    if j < minA or j > sumA:
        print('no')
    else:
        if solve(0, j):
            print('yes')
        else:
            print('no')

Solution (Python):
import sys
sys.setrecursionlimit(100000)  
 


n=int(input())
A=[int(x) for x in input().split()]
minA=min(A)  
sumA=sum(A)  


 
q=int(input())
M=[int(x) for x in input().split()]
 
 
def solve(i,m):
    global n
    global A
    global minA
    global sumA
     
    if m<0 or m>sumA:
        return False
    if m==0:
        return True
    if i>=n:
        return False
     
    return solve(i+1,m) or solve(i+1,m-A[i])
     
     
for m in M:
    if m<minA or m>sumA: 
        print('no')
    else:
        if solve(0,m):
            print('yes')
        else:
            print('no')

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

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

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

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

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

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

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

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

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

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

max = 2000

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

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

Solution (Python):
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")

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

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

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

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

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

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

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

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

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

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


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


def search(q):
    sum_ary = [0]

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

    else:
        return False


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

Solution (Python):

import itertools

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

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

sum1=set()

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

Solution (Python):


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

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
*A, = map(int, input().split())
q = int(input())
*Q, = map(int, input().split())
 
bits = 1
for a in A:
    bits |= bits << a
 
for q in Q:
    print("yes"*((bits >> q) & 1)or"no")

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
q = int(input())
m = list(map(int,input().split()))
 
def solve(i, m_i):
    if m_i == 0:
        return True
    if i >= n:
        return False
    res = solve(i + 1, m_i) or solve(i + 1, m_i - a[i])
    return res
 
for m_tmp in m:
    if sum(a) < m_tmp:
        print("no")
    elif solve(0, m_tmp):
        print("yes")
    else:
        print("no")

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

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

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

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

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

sumA = sum(a)

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

Solution (Python):
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)])

    
    

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


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

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


def memoize(f):
    cache = {}

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


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


@memoize
def solve(i, m):
    if m == 0:
        return True

    if i >= n:
        return False

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


if __name__ == '__main__':
    main()

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

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

def memolize(f):
    cache = {}

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

@memolize
def solve(i, m):
    if m == 0:
        return True

    if i >= n:
        return False

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

if __name__ == '__main__':
    main()

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

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

def memolize(f):
    cache = {}

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

@memolize
def solve(i, m):
    if m == 0:
        return True

    if i >= n:
        return False

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

if __name__ == '__main__':
    main()

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

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

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

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

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

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

	res = False

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

	memo[key] = res		
	return res

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

Solution (Python):

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

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

	res = False

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

	dict[key] = res		
	return res

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

Solution (Python):

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

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

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

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

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

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

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

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

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

Solution (Python):

from __future__ import division, print_function
from sys import stdin
from itertools import combinations


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


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

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

Solution (Python):


from __future__ import print_function,division
from itertools import combinations
import time
import sys
import io
import re
import math
start = time.clock()
i = 0
def enum_sum_numbers(sets, s_range, r):
    for cmb in combinations(sets,r):
        yield sum(cmb)
    if r <=s_range:
        for s in enum_sum_numbers(sets,s_range, r+1):
            yield s

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

Solution (Python):


from __future__ import print_function,division
import time
import sys
import io
import re
import math
start = time.clock()
i = 0

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

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

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

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

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

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

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

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

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

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

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

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
m = int(input())
q = list(map(int,input().split()))
cand = []
for i in range(2**n):
    tmp = 0
    for j in range(n):
        if(i>>j)&1:
            tmp += a[j]
    if tmp not in cand:
        cand.append(tmp)
for i in q:
    print('yes' if i in cand else 'no')

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

pattern=[]

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

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

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

result = []

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

    result.append(score)

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