Problem:


Exhaustive Search

Write a program which reads a sequence A of n elements and an integer M, and outputs "yes" if you can make M by adding elements in A, otherwise "no". You can use an element only once.

You are given the sequence A and q questions where each question contains Mi.

Input

In the first line n is given. In the second line, n integers are given. In the third line q is given. Then, in the fourth line, q integers (Mi) are given.

Output

For each question Mi, print yes or no.

Constraints

n ≤ 20

 q ≤ 200 

1 ≤ elements in A ≤ 2000

1 ≤ Mi ≤ 2000

Sample Input 1

5
1 5 7 10 21
8
2 4 17 8 22 21 100 35

Sample Output 1

no
no
yes
yes
yes
yes
no
no

Notes

You can solve this problem by a Burte Force approach. Suppose solve(p, t) is a function which checkes whether you can make t by selecting elements after p-th element (inclusive). Then you can recursively call the following functions:

solve(0, M) 

solve(1, M-{sum created from elements before 1st element}) 

solve(2, M-{sum created from elements before 2nd element}) 

...

The recursive function has two choices: you selected p-th element and not. So, you can check solve(p+1, t-A[p]) and solve(p+1, t) in solve(p, t) to check the all combinations.

For example, the following figure shows that 8 can be made by A[0] + A[2].

Template in C
-->



Sample input:
5
1 5 7 10 21
8
2 4 17 8 22 21 100 35


Sample output:
no
no
yes
yes
yes
yes
no
no

Submission status: Accepted

Solution code:
is_able_make = [False]*2000

input()

A = [ int( val ) for val in input().rstrip().split( ' ' ) ]
q = int(input())
M = [ int( val ) for val in input().rstrip().split( ' ' ) ]

for i in A:
    for j in range(2000-i,0,-1):
        if is_able_make[j] == True:
            is_able_make[i+j] = True
    is_able_make[i] = True

for x in M:
    if(is_able_make[x] == True):
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
#coding:utf-8
#1_5_A
from itertools import combinations

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

numbers = []
for i in range(1, n+1):
    for com in combinations(A, i):
        numbers.append(sum(com))

for m in ms:
    if m in numbers:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
#coding:utf-8
#1_5_A
from itertools import combinations

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

numbers = set()
for i in range(1, n+1):
    for com in combinations(A, i):
        numbers.add(sum(com))

for m in ms:
    if m in numbers:
        print("yes")
    else:
        print("no")

Submission status: Accepted

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


S = [0]*len(A)
flags = [False]*len(M)
def brute_force(n):
    if n == len(S):
        ans = 0
        for i in range(len(S)):
            if S[i] == 1: ans += A[i]
        for i in range(len(M)):
            if ans == M[i]: flags[i] = True
    else:
        S[n] = 0
        brute_force(n+1)
        S[n] = 1
        brute_force(n+1)


brute_force(0)

for flag in flags:
    if flag: print "yes"
    else: print "no"

Submission status: Accepted

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

memo = []
for i in range(len(A)+1):
    memo.append([None]*2000)

def solve(i,m):
    if memo[i][m] != None: return memo[i][m]
    if m == 0:
        memo[i][m] = True
        return True
    elif i >= n:
        memo[i][m] = False
        return False
    else:
        ret = solve(i+1,m) | solve(i+1,m-A[i])
        memo[i][m] = ret
        return ret

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

Submission status: Accepted

Solution code:
def solve(A, i, m, n):
    """Return if it is possible to make value m with some elements in A.

    n is length of A.
    i is index.
    Using Divide-and-Conquer method.
    """

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


import sys

n = int(sys.stdin.readline())
A = tuple(map(int, sys.stdin.readline().split()))
q = sys.stdin.readline()
M = tuple(map(int, sys.stdin.readline().split()))

s_A = sum(A)

ans = ''

for m in M:
    if s_A < m:
        ans += 'no\n'
    elif solve(A, 0, m, n):
        ans += 'yes\n'
    else:
        ans += 'no\n'

print(ans, end = '')

Submission status: Accepted

Solution code:
def solve(A, i, m, n):
    """Return if it is possible to make value m with some elements in A.

    n is length of A.
    i is index.
    R is the record of answer i, m.
    Using Divide-and-Conquer method.
    """

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


import sys

n = int(sys.stdin.readline())
A = tuple(map(int, sys.stdin.readline().split()))
q = int(sys.stdin.readline())
M = tuple(map(int, sys.stdin.readline().split()))

s_A = sum(A)
R = [[None] * 2000 for i in range(n + 1)]

ans = ''

for m in M:
    if s_A < m:
        ans += 'no\n'
    elif solve(A, 0, m, n):
        ans += 'yes\n'
    else:
        ans += 'no\n'

print(ans, end = '')

Submission status: Accepted

Solution code:
# coding: utf-8
N = int(input())
A = [int(i) for i in input().split()]
q = int(input())
m = [int(i) for i in input().split()]
MAX_LENGTH = len(A)
dp = [[-1 for i in range(max(m) + 1)] for j in range(MAX_LENGTH + 1)]
# i番目以降の値を使ってmを作ればTrueを返す
def fullSearch(i, m):
    # 終了条件
    if m < 0:
        return False
    elif dp[i][m] != -1:
        return dp[i][m]
    elif m == 0:
        return True
    elif i >= MAX_LENGTH:
        return False
    else:
        # 全探索かっこわるい
        res = fullSearch(i + 1, m) or fullSearch(i + 1, m - A[i])
    # のでメモ化
    dp[i][m] = res
    return res
for mi in m:
    print("yes" if fullSearch(0, mi) else "no")

Submission status: Accepted

Solution code:
from itertools import combinations

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

cache = {}


def sum_a(tmp, t):
    global a, cache
    if t in cache:
        return tmp + cache[t]
    elif len(t) == 1:
        return tmp + a[t[0]]
    else:
        cache[t] = result = sum_a(tmp + a[t[0]], t[1:])
        return result


l = list(sum_a(0, t) for i in range(n) for t in combinations(range(n), i + 1))

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

Submission status: Accepted

Solution code:
from itertools import combinations

n, a, q, ms, cache = int(input()), list(map(int, input().split())), input(), map(int, input().split()), {}


def sum_a(tmp, t):
    global a, cache
    if t in cache:
        return tmp + cache[t]
    elif len(t) == 1:
        return tmp + a[t[0]]
    else:
        cache[t] = result = sum_a(tmp + a[t[0]], t[1:])
        return result


l = set(sum_a(0, t) for i in range(n) for t in combinations(range(n), i + 1))

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

Submission status: Accepted

Solution code:
from itertools import combinations

n, a, q, ms, cache = int(input()), list(map(int, input().split())), input(), map(int, input().split()), {}

l = set(sum(t) for i in range(n) for t in combinations(a, i + 1))

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

Submission status: Accepted

Solution code:
from itertools import combinations

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

l = set(sum(t) for i in range(n) for t in combinations(a, i + 1))

for m in map(int, input().split()):
    print('yes' if m in l else 'no')

Submission status: Accepted

Solution code:
n = input()

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

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

def solve(i, m):
   if m == 0:
     return True
   if i >= n or m > sum(A):
     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: Accepted

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

def solve(i, m):
    if m == 0:
        return 1
    if i >= n or m > sum(A):
        return 0
    res = solve(i + 1, m) or solve(i + 1, m - A[i])
    return res
        
for j in range(0, q):
    if solve(0, m[j]):
        print "yes"
    else:
        print "no"

Submission status: Accepted

Solution code:
def check(m,g,A,n):
    
    for i in range(n):
        gg = g + A[n-i-1]
        if m == gg:
            return True
        elif n == 0 or m < gg:
            continue
        if check(m,gg,A,n-i-1) == True:
            return True
    return False
        

    

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




mini = min(A)
nor = sum(A)

for mi in m:
    if mi < mini or mi > nor:
        print("no")
        continue
    if check(mi,0,A,n):
        print("yes")
    else:
        print("no")

Submission status: Accepted

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

def func(i, p):
  if i != n:
    func(i+1, p)
    p += A[i]
    func(i+1, p)
  elif i == n:
    nums.append(p)

func(0, 0)

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

Submission status: Accepted

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

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

for j in range(0, q):
 if solve(0, m[j]):
  print 'yes'
 else:
  print 'no'

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

n2 = input()
q = map(int, raw_input().split())

list = set()

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

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

Submission status: Accepted

Solution code:
def solve(i, m):
  if dp[i][m] != -1:
    return dp[i][m]

  if m == 0:
    dp[i][m] = 1
  elif i >= n:
    dp[i][m] = 0
  elif solve(i+1, m):
    dp[i][m] = 1
  elif solve(i+1, m-A[i]):
    dp[i][m] = 1
  else:
    dp[i][m] = 0

  return dp[i][m]



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

dp = [[-1 for col in range(2000)] for row in range(n+1)]

for i in range(p):
  if solve(0, m[i]):
    print 'yes'
  else:
    print 'no'

Submission status: Accepted

Solution code:
n = int(raw_input())
A = map(int,raw_input().split())
q = int(raw_input())
m = map(int,raw_input().split())
 
def solve(i,m):
    if m == 0:
        return 1
    if i >= n or m - sum(A) > 0:
        return 0
    res = solve(i+1,m) or solve(i+1,m-A[i])
    return res
 
for j in range(q):
    if solve(0,m[j]):
        print "yes"
    else:
        print "no"

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n = int(raw_input())
A = map(int, raw_input().split())
q = int(raw_input())
m = map(int, raw_input().split())
 
def solve(i, m):
    if m == 0:
        return 1
    if i  >= n or m > sum(A):
        return 0
    res = solve(i + 1, m) or solve(i + 1, m - A[i])
    return res
         
for j in range(0, q):
    if solve(0, m[j]):
        print "yes"
    else:
        print "no"

Submission status: Accepted

Solution code:

        
def solve(i,m):
    if dp[i][m] != -1:
        return dp[i][m]
    if m == 0:
        dp[i][m] = True
    elif i >= n:
        dp[i][m] = False
    elif solve(i+1, m):
        dp[i][m] = True
    elif solve(i+1, m-a[i]):
        dp[i][m] = True
    else:
        dp[i][m] = False
    return dp[i][m]

n = input()
a = map(int,raw_input().split())
q = input()
p = map(int,raw_input().split())
dp = [[-1 for i in xrange(2001)] for j in xrange(21)]
for i in xrange(q):
    if solve(0,p[i]):
        print "yes"
    else:
        print "no"

Submission status: Accepted

Solution code:
n = int(raw_input())
A = map(int, raw_input().split())
q = int(raw_input())
M = map(int, raw_input().split())
  
def solve(i,m):
  if m == 0:
    return True
  if i >= n or m - sum(A) > 0:
    return False
  res = solve(i+1,m) or solve(i+1, m-A[i])
  return res

for j in range(q):
   if solve(0,M[j]):
      print "yes"
   else:
      print "no"

Submission status: Accepted

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

a = [[0 for j in range(max(m) + 1)] for i in range(n)]

for i in range(n):
    for j in range(max(m) + 1):
        if (i == 0):
            temp = A[i]
            if (temp <= j):
                a[i][j] = temp
            else:
                a[i][j] = 0
        else:
            temp1 = 0
            temp2 = 0
            if (j - A[i] >= 0):
                temp1 = a[i-1][j - A[i]] + A[i]
            temp2 = a[i-1][j]
            a[i][j] = max(temp1, temp2)

for i in range(q):
    if (a[n-1][m[i]] == m[i]):
        print "yes"
    else:
        print "no"

Submission status: Accepted

Solution code:

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

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

result = []
for i in range(q):
    result.append('no')

def adder(axis = 0, nums = [0], M = [0], q = 0):
    for i in range(q):
        if M[i] == axis:
            result[i] = 'yes'
    length = len(nums)
    if length != 0:
        for i in range(length):
            sum_n = axis + nums[i]
            adder(sum_n, nums[i+1:], M, q)

for i in range(n):
    adder(A[i], A[i+1:], M, q)

for i in result:
    print(i)

Submission status: Accepted

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

def solve(i, m):
  if m == 0:
    return True
  elif i >= n or m > sum(A):
    return False

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

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

Submission status: Accepted

Solution code:

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

Solution code:
n = int(raw_input())
A = map(int, raw_input().split())
q = int(raw_input())
m = map(int, raw_input().split())
  
def ans(i, m):
    if m == 0:
        return 1
    if i  >= n or m > sum(A):
        return 0
    res = ans(i + 1, m) or ans(i + 1, m - A[i])
    return res
          
for j in range(0, q):
    if ans(0, m[j]):
        print "yes"
    else:
        print"no"

Submission status: Accepted

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

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

for j in range(Q):
  if s(0, m[j]):
    print "yes"
  else:
    print "no"

Submission status: Accepted

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

def solve(j, m):
  if m == 0:
    return 1
  if j >= n or m > sum(A):
    return 0
  res = solve(j + 1, m) or solve(j + 1, m - A[j])
  return res

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

Submission status: Accepted

Solution code:
def ans(n, AA, x):
    tmp = n + AA[0]
    if len(AA) == 1:
        try: x[tmp] = 1
        except: pass
    else:
        ans(n, AA[1:], x)
        try:
            x[tmp] = 1
            ans(tmp, AA[1:],x)
        except:
            pass
    return
 
n = raw_input()
A = map(int, raw_input().split())
q = raw_input()
M = map(int, raw_input().split())
 
x = [0 for i in range(max(M)+1)]
ans(0, A, x)
 
for e in M:
    if x[e] == 1:
        print 'yes'
    else:
        print 'no'

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:


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

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

def ans(i, m):
    if m == 0:
        return 1
    if i  >= n or m > sum(A):
        return 0
    res = ans(i + 1, m) or ans(i + 1, m - A[i])
    return res
           
for j in range(0, q):
    if ans(0, M[j]):
        print "yes"
    else:
        print"no"

Submission status: Accepted

Solution code:
n = int(input())
a = map(int,raw_input().split())
p = int(input())
m = map(int,raw_input().split())
def goukei(i,m):
  if m ==0:
    return True
  if i >= n or m > sum(a):
    return False
  r = goukei(i + 1, m) or goukei(i + 1, m - a[i])
  return r
 
for u in range(0,p):

  if goukei(0, m[u]):
    print "yes"
  else:
    print "no"

Submission status: Accepted

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

Submission status: Accepted

Solution code:


n = int(raw_input())
A = map(int, raw_input().strip().split(' '))
q = int(raw_input())
M = map(int, raw_input().strip().split(' '))
 
memo = []
for i in range(len(A)+1):
    memo.append([None]*2000)
 
def solve(i,m):
    if memo[i][m] != None: return memo[i][m]
    if m == 0:
        memo[i][m] = True
        return True
    elif i >= n:
        memo[i][m] = False
        return False
    else:
        ret = solve(i+1,m) | solve(i+1,m-A[i])
        memo[i][m] = ret
        return ret
 
for m in M:
    if solve(0,m): print "yes"
    else: print "no"

Submission status: Accepted

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 = sorted(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: Accepted

Solution code:
n = int(raw_input())
A = map(int, raw_input().split())
d = {}
 
def soleve(i, m, n):
    if m == 0:
        return True
    if i >= n:
        return False
    if d.has_key((i, m)):
        return d[(i, m)]
    res = soleve(i + 1, m, n) or soleve(i + 1, m - A[i], n)
    d[(i, m)] = res
    return res
 
 
q = int(raw_input())
M = map(int, raw_input().split())
for m in M:
    if soleve(0, m, n):
        print 'yes'
    else:
        print 'no'

Submission status: Accepted

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

def solve(i, m):
    if m == 0:
        return True
    if n <= i or sum(A) < m:
        return False
    x = (solve(i+1, m) or solve(i+1, m-A[i]))
    return  x
 
for m in M:
    if solve(0, m):
        print "yes"
    else:
        print "no"

Submission status: Accepted

Solution code:
num_n = int(input())
n = map(int, raw_input().split())
num_m = int(input())
m = map(int, raw_input().split())
    
def solve(i, m):
   if m == 0:
      return True
   if i >= num_n or m > sum(n):
      return False
   res = solve(i + 1, m) or solve(i + 1,m - n[i])
   return res
     
for k in range(num_m):
   if solve(0, m[k]):
      print "yes"
   else:
      print "no"

Submission status: Accepted

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:
    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: Accepted

Solution code:
num_n = int(input())
n = map(int, raw_input().split())
num_m = int(input())
m = map(int, raw_input().split())
     
def solve(i, m):
   if m == 0:
      return True
   if i >= num_n or m > sum(n):
      return False
   res = solve(i + 1, m) or solve(i + 1,m - n[i])
   return res
      
for k in range(num_m):
   if solve(0, m[k]):
      print "yes"
   else:
      print "no"

Submission status: Accepted

Solution code:
n = input()
A = map(int, raw_input().split())
q = input()
M = map(int, raw_input().split())
    
def solve(i, m):
  if m==0:
    return True
  if i>=n or m>sum(A):
    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: Accepted

Solution code:
def solve(i, m):
  if dp[i][m] != -1:
    return dp[i][m]
 
  if m == 0:
    dp[i][m] = 1
  elif i >= n:
    dp[i][m] = 0
  elif solve(i+1, m):
    dp[i][m] = 1
  elif solve(i+1, m-A[i]):
    dp[i][m] = 1
  else:
    dp[i][m] = 0
 
  return dp[i][m]
 
 
 
n = input()
A = map(int, raw_input().split())
p = input()
m = map(int, raw_input().split())
 
dp = [[-1 for col in range(2000)] for row in range(n+1)]
 
for i in range(p):
  if solve(0, m[i]):
    print 'yes'
  else:
    print 'no'

Submission status: Accepted

Solution code:
input()
A = [int(x) for x in input().split()]
input()
ms = [int(x) for x in input().split()]

enable_create = [False]*2000
for bit in range(1 << len(A)):
    n = 0
    for i in range(len(A)):
        if 1 & (bit >> i) == 1:
            n += A[i]
    enable_create[n] = True

for m in ms:
    print("yes" if enable_create[m] else "no")

Submission status: Accepted

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: Accepted

Solution code:
import time

def sum_A(A, n):
    dic = {}
    
    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: Accepted

Solution code:
import time

def sequence(A, n):
    dic = {}
    
    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())

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

Submission status: Accepted

Solution code:
def sequence(A, n):
    dic = {}
    
    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())

    solve = sequence(A, n)
    for m_i in m:
        print "yes" if solve(0, m_i) else "no"

Submission status: Accepted

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

R = [[None] * 2000 for i in range(n + 1)]

def solve(A, i, m, n):
    if R[i][m] != None:
        return R[i][m]
    if m == 0:
        R[i][m] = True
        return True
    elif i >= n:
        R[i][m] = False
        return False
    else:
        ans = solve(A, i + 1, m, n) or solve(A, i + 1, m - A[i], n)
        R[i][m] = ans
        return ans

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

Submission status: Accepted

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

R = [[None for j in range(2000)] for i in range(n + 1)]

def solve(i, m):
    if R[i][m] != None:
        return R[i][m]
    if m == 0:
        R[i][m] = True
        return True
    elif i > n - 1:
        R[i][m] = False
        return False
    else:
        ans = solve(i + 1, m) or solve(i + 1, m - A[i])
        R[i][m] = ans
        return ans

sum_A = sum(A)
for i in M:
    if sum_A < i:
        print('no')
    elif solve(0, i):
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
import sys

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

    return exhaustiveSearch(A, m, i + 1, s) or exhaustiveSearch(A, m - A[i], i + 1, s)

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

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

Submission status: Accepted

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

n = int(raw_input())
A = {0}
for c in raw_input().split():
    for i in A.copy():
        A.add(i+int(c))
q = int(raw_input())
M = map(int, raw_input().split())
for m in M:
    if m in A:
        print "yes"
    else:
        print "no"

Submission status: Accepted

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

from itertools import repeat
from itertools import combinations

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

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

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


def makeCache(s):
    cache = {}
    for i in range(len(s)):
        comb = list(combinations(s, i))
        for c in comb:
            cache[sum(c)] = 1

    return cache

def loop(s, m):
    for i in range(len(s)):
        comb = list(combinations(s, i))
        for c in comb:
            if sum(c) == m:
                return 1

    return 0

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()]
    s = makeCache(a)
    for i in m:
        #print("yes") if rec(a, 0, 0, i) > 0 else print("no")
        #print("yes") if loop(a, i) > 0 else print("no")
        print("yes") if i in s else print("no")

Submission status: Accepted

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

if __name__=='__main__':
    n=int(input()) 
    A=list(map(int,input().split()))
    q=int(input()) 
    Q=list(map(int,input().split()))
    for m in Q:
        if   m > sum(A): print('no')
        elif solve(m,A): print('yes') 
        else           : print('no')

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
memo = [[None]*2000 for i in range(2000)]


def exhaustivesearch(i, target):
    if memo[i][target] is not None:
        return memo[i][target]
    if target == 0:
        memo[i][target] = True
        return True
    if i >= n:
        memo[i][target] = False
        return False
    else:
        memo[i][target] = exhaustivesearch(i + 1, target) or exhaustivesearch(i + 1, target-A[i])
        return memo[i][target]


for j in m:
    if exhaustivesearch(0, j):
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
is_able_make = [False] * 2000
n = int(input())
A = [int(i) for i in input().split()]
q = int(input())
M = [int(i) for i in input().split()]

for i in A:
    for j in range(2000-i, 0, -1):
        if is_able_make[j] == True:
            is_able_make[i+j] = True
    is_able_make[i] = True

for x in M:
    if is_able_make[x] == True:
        print('yes')
    else:
        print('no')