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:
from itertools import combinations

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

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

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

Submission status: Accepted

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

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

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

for m in M:
    if m in s:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
from functools import lru_cache

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

@lru_cache(maxsize=None)
def solve(i, m):
    if m == 0:
        return True
    elif i >= n or m < A[i]:
        return False
    else:
        return solve(i + 1, m - A[i]) or solve(i + 1, m)

for m in query:
    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.
    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
# Here your code !
n=int(input())
A=[int(i) for i in input().split()]
q=int(input())
m=[int(i) for i in input().split()]


from itertools import combinations
x=[]
for i in range(len(A)):
    t=(list(combinations(A,i)))
    x.append(t)
combi=set()
for i in x:
    for j in i:
        combi.add(sum(j))

for i in m:
    if i in combi:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
from functools import lru_cache

@lru_cache(maxsize = 10000)
def canProd(i,m):
     
    if m == 0:
        return True
    if i >= n:
        return False
 
    res = canProd(i+1,m) or canProd(i+1,m-a[i])
    return res
 
 
n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
m = [int(x) for x in input().split()]
 
for i in m:
    if canProd(0,i):
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
from functools import lru_cache

@lru_cache(maxsize = None)
def canProd(i,m):
     
    if m == 0:
        return True
    if i >= n:
        return False
 
    res = canProd(i+1,m) or canProd(i+1,m-a[i])
    return res
 
 
n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
m = [int(x) for x in input().split()]

rs = [None]*2001

maxm = max(m)
minm = min(m)

for i in range(minm,maxm+1):
    if canProd(0,i):
        rs[i] = "yes"
    else:
        rs[i] = "no"

for i in m:
    print(rs[i])

Submission status: Accepted

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

Submission status: Accepted

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

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

for m_tmp in m:
    if sum(a) < m_tmp:
        print('no')
    elif solve(0,m_tmp):
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
def ALDS1_5A():
    n, A, q = int(input()),list(map(int, input().split())), int(input())
    allFromA = [False]*2001
    for a in A:
        for i in range(2000-a, 0, -1):
            if allFromA[i]:
                allFromA[i+a] = True
        allFromA[a] = True

    for m in input().split():
        if allFromA[int(m)]:
            print('yes')
        else:
            print('no')

if __name__ == '__main__':
    ALDS1_5A()

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int, input().split()))
q = int(input())
t = list(map(int, input().split()))

record = [False] * 2001
for item in s:
    for i in range(2000 - item, 0, -1):
        if record[i]:
            record[i + item] = True
    record[item] = True

for m in t:
    if record[m]:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
a_len = int(input())
a_ar = sorted([int(n) for n in input().split(" ")])
b_len = int(input())
b_ar = [int(n) for n in input().split(" ")]
dp = [0 for n in range(2001)]
for a in a_ar:
    new_dp = dp[:]
    new_dp[a] = 1
    for i,d in enumerate(dp):
        if d and i + a <= 2000:
            new_dp[i + a] = 1
    dp = new_dp
for b in b_ar:
    if dp[b]:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
a_len = int(input())
a_ar = sorted([int(n) for n in input().split(" ")])
b_len = int(input())
b_ar = [int(n) for n in input().split(" ")]
dp = [0 for n in range(2001)]
for a in a_ar:
    new_dp = dp[:]
    new_dp[a] = 1
    for i,d in enumerate(dp):
        if d and i + a <= 2000:
            new_dp[i + a] = 1
        elif i + a > 2000:
            break
    dp = new_dp
for b in b_ar:
    if dp[b]:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
a_len = int(input())
a_ar = sorted([int(n) for n in input().split(" ")])
b_len = int(input())
b_ar = [int(n) for n in input().split(" ")]
max_b = max(b_ar)
dp = [0 for n in range(max_b + 1)]
for a in a_ar:
    new_dp = dp[:]
    new_dp[a] = 1
    for i,d in enumerate(dp):
        if d and i + a <= max_b:
            new_dp[i + a] = 1
    dp = new_dp
for b in b_ar:
    if dp[b]:
        print("yes")
    else:
        print("no")

Submission status: Accepted

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


def exhaustive(lst, size):
    result = []
    for i in range(0, 1 << size):
        total = 0
        for j in range(0, size):
            if (i & 0x01) == 1:
                total += lst[j]
            i = i >> 1
        result.append(total)
    return result


if __name__ == "__main__":
    lst = [val.split() for val in sys.stdin.read().splitlines()]
    n, data, m, targets = [[int(n) for n in inner_lst] for inner_lst in lst]
    result = exhaustive(data, int(n[0]))
    print("\n".join(["yes" if x in result else "no" for x in targets]))

Submission status: Accepted

Solution code:
def solve(i, m):
    if m == 0: return True

    if i < n and min(A[i:]) <= m <= sum(A[i:]):
        r1 = solve(i + 1, m-A[i])
        if r1: return r1
        r2 = solve(i + 1, m)
        if r2: return r2


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

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

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

Submission status: Accepted

Solution code:
def ALDS1_5A():
    n, A, q = int(input()), list(map(int, input().split())), int(input())
    S=[False for i in range(2001)]
    for a in A:
        for i in range(2001-a, 0, -1):
            if S[i]: S[i+a] = True
        S[a] = True
    for mi in input().split():
        if S[int(mi)]:
            print('yes')
        else:
            print('no')

if __name__ == '__main__':
    ALDS1_5A()

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

add_result = [0]*2001
for i in a:
	for j in range(2000, -1, -1):
		if add_result[j] == 1:
			add_result[i+j] = 1
			#print(i, j, i+j)	
	add_result[i] = 1
	#print i

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

Submission status: Accepted

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

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

for m in mi:
    if solve(0, m):
        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()))

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 tmp_m in m:
  if sum(A) < tmp_m:
    print('no')
  elif solve(0, tmp_m):
    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()))

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

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

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

Submission status: Accepted

Solution code:
from itertools import product


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

    dp(n, A, q, M)


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


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

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


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

    return False


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations
n = int(input())
A = tuple(map(int, input().split()))
B = set(A)
for i in range(2, n + 1):
    for C in combinations(A, i):
        B.add(sum(C))
q = int(input())
for m in map(int, input().split()):
    print("yes" if m in B else "no")

Submission status: Accepted

Solution code:
n = int(input())
SET1 = {0}
for a in map(int, input().split()):
    for b in tuple(SET1):
        SET1.add(a + b)
input()
for m in map(int, input().split()):
    print('yes' if m in SET1 else 'no')

Submission status: Accepted

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


if __name__ == '__main__':

    n = int(input())
    A = [int(a) for a in input().split(" ")]
    q = int(input())
    M = [int(m) for m in 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

    ans = []
    for m in M:
        if solve(0, m):
            ans.append("yes")
        else:
            ans.append("no")

    print("\n".join(ans))

Submission status: Accepted

Solution code:
A_count = int(input());
A = [int(n) for n in input().split()];
M_count = int(input());
M = [int(n) for n in input().split()];

memo = [[None for i in range(2000)] for j in range(A_count + 1)];

def solve(start, target):
    if memo[start][target] is not None:
        return memo[start][target];
    if target == 0:
        return True;
    elif start >= A_count:
        return False;
    else:
        result = solve(start + 1, target) or solve(start + 1, target - A[start]);
        if result:
            memo[start][target] = True;
            return True;
        else:
            memo[start][target] = False;
            return False;

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

Submission status: Accepted

Solution code:
a = []
d = {}

def decode():
    global a

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

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

    return n, a, q, ms


def solve(i, m):
    global a, d

    if (i, m) in d:
        return d[(i, m)]

    if a[i] == m:
        d[(i, m)] = True
        return True
    else:
        if i < len(a) - 1:

            if solve(i+1, m) or (m - a[i] > 0 and solve(i+1, m-a[i])):
                d[(i, m)] = True
                return True
            else:
                d[(i, m)] = False
                return False

        else:
            d[(i, m)] = False
            return False


if __name__ == '__main__':

    n, a, q, ms = decode()
    for m in ms:
        if solve(0, m):
            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(' ')))

dp = {}

# Aの要素のうちp番目以降を組み合わせてtを作れるか?
def solve(p, t):
  if ((p, t) in dp):
    return dp[(p, t)]

  if (p == n):
    # 使う/使わないの枝をたどって0になったらOK
    return t == 0

  # p番目を使ったらtを引いて次へ, 使わなければtのまま次へ
  ans = solve(p+1, t-A[p]) or solve(p+1, t)
  dp[(p, t)] = ans
  return ans

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

Submission status: Accepted

Solution code:
num_n = int(input())
n = [int(x) for x in input().split()]
num_m = int(input())
m = [int(x) for x in 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:
_ = int(input())
hoge = [int(x) for x in input().split()]
_ = int(input())

def exSearch(i, m):
    if m == 0:
        return True
    if i >= len(hoge) or m > sum(hoge):
        return False
    res = exSearch(i+1, m) or exSearch(i+1, m-hoge[i])
    return res

if __name__ == '__main__':
    
    for val in (int(x) for x in input().split()):
        if exSearch(0, val):
            print ('yes')
        else:
            print ('no')

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
r=[]
def f(s,k):
    if k>=0:
        global r
        r+=[s]
        f(s+A[k-1],k-1)
        f(s,k-1)
f(0,n)
input()
for e in map(int,input().split()):print(['no','yes'][e in r])

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
r=set()
def f(s,k):
    if k>=0:
        global r
        r.add(s)
        f(s+A[k-1],k-1)
        f(s,k-1)
f(0,n)
input()
for e in map(int,input().split()):print(['no','yes'][e in r])

Submission status: Accepted

Solution code:
input()
s = {0}
for a in map(int,input().split()):
    for b in list(s):
        s.add(a+b)
input()
for e in map(int,input().split()):
    print('yes' if e in s else 'no')

Submission status: Accepted

Solution code:
input()
s={0}
for a in map(int,input().split()):
 for b in list(s):s.add(a+b)
input()
for e in map(int,input().split()):print(['no','yes'][e in s])

Submission status: Accepted

Solution code:
input()
s={0}
for a in map(int,input().split()):
 for b in list(s):s.add(a+b)
input()
for e in input().split():print(['no','yes'][int(e)in s])

Submission status: Accepted

Solution code:
b=1
input()
for a in map(int,input().split()):b|=b<<a
input()
for m in map(int,input().split()):print(['no','yes'][(b>>m)&1])

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

def solve(p, t, A, result):
    if A[p] == t:
        result[(p,t)] = True
        return True
    if p == len(A) - 1:
        return False
    if (p,t) in result:
        # print('Cache Hit')
        return result[(p,t)]
    if solve(p+1, t-A[p], A, result):
        result[(p,t)] = True
        return True
    if solve(p+1, t, A, result):
        result[(p,t)] = True
        return True
    result[(p,t)] = False 
    return False

import sys

n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
num_q = int(sys.stdin.readline())
query = list(map(int, sys.stdin.readline().split()))
result = dict()

for m in query:
    if solve(0, m, A, result):
        print('yes')
    else:
        print('no')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

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

Submission status: Accepted

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

    tree = Tree(ns)
    _ = int(input())  # flake8: noqa

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



if __name__ == '__main__':
    run_tree()

Submission status: Accepted

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

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


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

    sums = create_sums(ns)
    _ = int(input())  # flake8: noqa

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


if __name__ == '__main__':
    run_set()

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
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):
        #print(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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)  # set the maximum depth as 10000

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def solve_knapsack_problem(A,n,m):
    a=[[0 for i in range(m+1)]for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,m+1):
            if A[i-1]<=j:
                a[i][j] = 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")

Submission status: Accepted

Solution code:
def search(l, m):
    #dp = [[None for _ in range(len(l) + 1)] for __ in range(m + 1)]
    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')

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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')