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:
n = int(input())

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

q = int(input())

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

ans = ["no"] * q

for i in range(2**n):
    now = 0
    for j in range(n):
        if i >> j & 1:
            now += a[j]

    if now in m.values():
        key_lst = [key for key, value in m.items() if value==now]
        for key in key_lst:
            ans[key] = "yes"

for i in range(q):
    print(ans[i])

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
m=int(input())
q=list(map(int,input().split()))
num_list=set()
for i in range(2**N):
    ans=0
    for j in range(N):
        if i>>j&1:
            ans+=A[j]
    num_list.add(ans)
for i in q:
    if i in num_list:
        print("yes")
    else:print("no")

Submission status: Accepted

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

able = [0] * (max(n * max(a) + 1, 2001))
for item in itertools.product([0, 1], repeat=n):
    total = sum([i * j for i, j in zip(a, item)])
    able[total] = 1

for m in M:
    print('yes' if able[m] else 'no')

Submission status: Accepted

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

s = set()
def check(i, m):
    if i == n:
        s.add(m)
        return
    check(i+1, m+A[i])
    check(i+1, m)

check(0,0)

for i in B:
    if i in s:
        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(" ")))
lst = []
for i in range(2 ** n, 0, -1):
    temp = 0
    for j in range(n):
        if (i >> j) & 1:
            temp += a[j]
    lst.append(temp)
for k in range(q):
    if m[k] in lst:
        print("yes")
    else:
        print("no")

Submission status: Accepted

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

ans = []

for bit in range(1<<n):
    tmp = 0
    for i in range(n):
        if bit & (1<<i):
            tmp += A[i]
    ans.append(tmp)

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

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
import bisect
import functools

@functools.lru_cache(None)
def dfs(i,sum_v,val):
    if i == n:
        return sum_v == val
    if dfs(i+1,sum_v,val):
        return True
    if dfs(i+1,sum_v + A[i],val):
        return True
    return False
n = int(input())
A = list(map(int,input().split()))
q = int(input())
m = list(map(int,input().split()))

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

Submission status: Accepted

Solution code:
# ALDS1_5_A.py


def rec(a, use):
    if use >= N:
        memo[a] = True
        return
    _next = A[use]
    rec(a+_next,use+1)
    rec(a,use+1)


N = int(input())
A = list(map(int, input().split()))
Q = int(input())
M = list(map(int, input().split()))

memo = [False]*2000
rec(0, 0)
# print(memo)
for i in M:
    if memo[i]:
        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()))
sumA = sum(A)
def solve(i,m):
    if m == 0:
        return 1
    if i >= n:
        return 0
    rec =  solve(i+1,m) or solve(i+1, m - A[i])
    return rec
for i in m:
    if i >= sumA:
        print("no")
    else:
        if solve(0,i):
            print("yes")
        else:
            print("no")

Submission status: Accepted

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

ans = []
for i in range(2**n):
    cnt = 0
    for j in range(n):
        if ((i>>j)&1): cnt += a[j]
    ans.append(cnt)
for x in q:
    print('yes' if (x in ans) else 'no')

Submission status: Accepted

Solution code:
import sys
from collections import deque

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

n = I()
A = LI()
q = I()
m = LI()
ans = 0
partial_sum = set()
for i in range(2 ** n):
    bit = [i>>j&1 for j in range(n)]
    partial_sum.add(sum(A[k]*bit[k] for k in range(n)))
for x in m:
    print('yes' if x in partial_sum else 'no')

Submission status: Accepted

Solution code:
# coding: utf-8
# 全探索


def solve(i, m):
    global A, n

    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__":
    n = int(input())
    A = [int(i) for i in input().split()]
    q = int(input())
    m = [int(i) for i in input().split()]
    total = sum(A)
    for m_i in m:
        if m_i > total:
            print('no')
        else:
            print('yes' if solve(0, m_i) else 'no')

Submission status: Accepted

Solution code:
from itertools import product

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


for a in product(*((x,0) for x in A)):
    a_sum.add(sum(a))

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

Submission status: Accepted

Solution code:
from itertools import product

n = int(input())
A = map(int,input().split())
sums = set(map(sum,product(*((0,a) for a in A))))
q = int(input())
for m in map(int,input().split()):
    print('yes' if m in sums else 'no')

Submission status: Accepted

Solution code:
n=int(input())
S=[int(i) for i in input().split()]
q=int(input())
T=[int(i) for i in input().split()]


def solve(i,m,n,S):
    if sum(S)<m:
        return False
        
    if m==0:
        return True

    elif i>=n:
        return False
        
    res=solve(i+1,m,n,S) or solve(i+1,m-S[i],n,S)
    return res
    
for i in range(q):
    attempt=solve(0,T[i],n,S)
    if attempt:
        print("yes")
        
    else:
        print("no")

Submission status: Accepted

Solution code:
from itertools import product

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

numbers = set()
for bits in product((0, 1), repeat=n):
    numbers.add(sum([a * b for a, b in zip(A, bits)]))

for m in M:
    if m in numbers:
        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 bitsearch():
  nums = [0] * (2 ** N)
  for i in range(2 ** N):
    num = 0
    for j in range(N):
      if (i >> j) & 1:
        num += A[j]
        nums[i] = num
  for q in range(Q):
    if M[q] in nums:
      print("yes")
    else:
      print("no")

bitsearch()

Submission status: Accepted

Solution code:
import itertools

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

data = []
for i in itertools.product(range(2),repeat=n):
    data.append(sum([i[j]*a[j] for j in range(n)]))
    
for i in m:
    if i in data:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
n = int(input())
A = [int(j) for j in input().split()]
q = int(input())
m = [int(j) for j in input().split()]
total = []
for i in range(2**n):
    bag = []
    for j in range(n):
        if ((i>>j)&1):
            bag.append(A[j])
    total.append(sum(bag))

for m1 in m:
    if m1 in set(total):
        print('yes')
    else:
        print('no')

Submission status: Accepted

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

sums = set()
from collections import deque
st = deque([[0, 0], [0, A[0]]])
while st:
    i, s = st.pop()
    i += 1
    if i == n:
        sums.add(s)
        continue
    st.append([i, s])
    st.append([i, s+A[i]])

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

Submission status: Accepted

Solution code:
def solve(m,ans):
    global L,S
    if m == len(L):
        S.add(ans)
    else:
        solve(m+1,ans+L[m])
        solve(m+1,ans)

n = int(input())
S = set([])
L = list(map(int,input().split()))
q = int(input())
solve(0,0)
for i in map(int,input().split()):
    if i in S:
        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()))

s = [list(map(int,bin(x)[2:].zfill(n))) for x in range(2**n)]

anset=set()
for j in s:
    ans=0
    for k in range(n):
        ans+=a[k]*j[k]
    anset.add(ans)

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

Submission status: Accepted

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

q = int(input())
m = [int(i) for i in input().split()]


def dfs(idx, s, target):
    if s == target:
        return 1
    if s > target or idx == n:
        return 0
    if s + sum(A[idx:]) < target:
        return 0

    return dfs(idx+1, s, target) or dfs(idx+1, s + A[idx], target)


for i in m:
    ans = 'yes' if dfs(0, 0, i) else 'no'
    print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n = int(input())
    t = list(map(int, input().split()))
    m = int(input())
    s = list(map(int, input().split()))

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

    for r in s:
        print('yes' if solve(0, r) else 'no')

Submission status: Accepted

Solution code:
def solve(i, m):

    if i >= n:
        combs.add(m)
        return

    solve(i+1, m)
    solve(i+1, m+A[i])


def main():
    global n
    global A
    global combs
    n = int(input())
    A = list(map(int, input().split()))
    _ = int(input())
    Q = list(map(int, input().split()))
    # 先に全部の組み合わせを計算しておくことで時間短縮
    combs = set()
    solve(0, 0)

    for q in Q:
        if q in combs:
            print("yes")
        else:
            print("no")


if __name__ == '__main__':
    main()

Submission status: Accepted

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

max = max(m)

dp = [[0 for _ in range(max + 1)] for __ in range(n + 1)]
dp[0][0] = 1#[1 for _ in range(max + 1)]
for j in range(n):
  for k in range(max + 1):
    if k >= A[j] and dp[j][k - A[j]]:
      dp[j + 1][k] = 1
    elif dp[j][k]:
      dp[j + 1][k] = 1
for i in range(q):
  if dp[n][m[i]]:
     print("yes")
  else:
    print("no")

Submission status: Accepted

Solution code:
from itertools import product

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

cases = product([0, 1], repeat=n)

seen = set()

for case in cases:
    sum_ = 0
    for i in range(n):
        sum_ += case[i] * A[i]
    seen.add(sum_)

for target in M:
    if target in seen:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
import sys


input = sys.stdin.readline


def make_sum_set(i, v):
    if i == N:
        S.add(v)
        return
    else:
        make_sum_set(i+1, v)
        make_sum_set(i+1, v+A[i])


def main():
    make_sum_set(0, 0)
    for m in M:
        if m in S:
            print("yes")
        else:
            print("no")


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()]
    S = set()
    main()

Submission status: Accepted

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

cnt = [0] * (2000 * 20)

for i in range(1, 2**n + 1):
    SUM = 0
    for j in range(n):
        if i>>j & 1:
            SUM += a[j]
    cnt[SUM] = 1

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

Submission status: Accepted

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

solved_dict = {}
n = int(input())
A = list(map(int, input().split()))
q = int(input())
for m in list(map(int, input().split())):
    print("yes" if solve(0, m) else "no")

Submission status: Accepted

Solution code:
import sys
from sys import stdin
input = stdin.readline

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

dp = [[-1 for i in range(2001)] for j in range(21)]

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]

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

Submission status: Accepted

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

def canmake(a,i):
    if(len(a)==1):
        if(a==i):
            return True
        else:
            return False

    for j in range(len(a)):
        ii = i-a[j]
        can=canmake(a[:j-1]+a[j+1:],ii) 
        if(can==True):
            return True
    return False   


def main(n,a,q,m):
    for i in m:
        ans=canmake(a,i)
        if(ans==True):
            print('yes')
        else:
            print('no')
    return

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

def main2(n,a,q,m):
    for mm in m:
        ans=solve(a,0,mm)
        if(ans==True):
            print('yes')
        else:
            print('no')


def main3():
    global n
    global a
    n=int(input())
    a=list(map(int,input().split()))
    q=int(input())
    ms=list(map(int,input().split()))
    for m in ms:
        ans=solve2(0,m)
        if(ans==True):
            print('yes')
        else:
            print('no')

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

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

    S = [0]*(2**n)
    #print(S)
    for i in range(2**n):
        b=1
        for j in range(n):
            #print(i,j,bin(b),i&b)
            if ( i&b == b):
                S[i] += a[j]
            b*=2
    #print(S)

    for mm in m:
        if (mm in S):
            print('yes')
        else:
            print('no')



if __name__=='__main__':
    #n,a,q,m = readinput()
    main4()

Submission status: Accepted

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

"""
def exhaustive_search(m, i):
    if i == n:
        return 0
    if m < 0:
        return 0
    if m == A[i]:
        return 1
    return max(exhaustive_search(m, i + 1), exhaustive_search(m - A[i], i + 1))
"""

def dp_search(m):
    dp = [[1] + [0] * m for _ in range(n + 1)] # dp[i][j] i番目まででjを作れるか
    for i in range(1, n+1):
        for j in range(1, m+1):
            if j >= A[i-1]:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - A[i-1]])
            else:
                dp[i][j] = dp[i-1][j]
    return dp[n][m]

for mi in m:
    if dp_search(mi):
        print("yes")
    else:
        print("no")

Submission status: Accepted

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

sum_set = set()
for i in range(1, 2 ** n):
    total = 0
    for j in range(n):
        if i >> j & 1:
            total += A[j]
    sum_set.add(total)

for num in nums:
    print('yes' if num in sum_set else 'no')

Submission status: Accepted

Solution code:
import itertools

n = input()
a = list(map(int, input().split()))
q = input()
 
aset = set()
for i in range(1, len(a) + 1):
    aset |= set(sum(combi) for combi in itertools.combinations(a, i))

for m in map(int, input().split()):
    print('yes' if m in aset 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()))
flag = [False] * 2000

for i in range(2 ** n):
    total = 0
    for j in range(n):
        if((i >> j) & 1):
            total += A[j]
    flag[total] = True
for m in M:
    print('yes' if flag[m] else 'no')

Submission status: Accepted

Solution code:
# ALDS_5_A - 総当たり　
import sys

n = int(input())
A = list(map(int, sys.stdin.readline().strip().split()))
q = int(input())
m = list(map(int, sys.stdin.readline().strip().split()))

sum_set = set()

for i in range(2 ** n):
    bit = [(i >> j) & 1 for j in range(n)]
    combined = [x * y for (x, y) in zip(A, bit)]
    sum_set.add(sum(combined))

for target in m:
    if target in sum_set:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

n = int(input())
A = [int(e) for e in input().split()]
q = int(input())
M = [int(e) for e in input().split()]

def solve(i,m):
    if m == 0:
        return True
    if i >= n:
        return False
    if m > sum(A[i:]):
        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(input())
a = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))

value = []
for i in range(2 ** n):
    ans = 0
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            ans += a[j]
    value.append(ans)  

for mm in range(len(m)):          
    if m[mm] in value:
        print("yes")
    else:
        print("no")

Submission status: Accepted

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

dp = []
for i in itertools.product([0, 1], repeat=n):
    tmp = 0
    for j in range(n):
        tmp += A[j] * i[j]
    dp.append(tmp)

for i in M:
    if i in dp:
        print('yes')
    else:print('no')

Submission status: Accepted

Solution code:
import itertools

def check(lst, n, x):
    for i in range(2, n+1):
        B = list(itertools.combinations(lst,i))
        for C in B:
            if x == sum(C):
                return True
    return False

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

for x in m:
    if x > sum(A):
        print("no")
    elif (x in A) or check(A, n, x):
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
dp = {}

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

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

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

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

  if m == 0:
    dp[(i, m)] = True
  elif n <= i:
    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)]

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

Submission status: Accepted

Solution code:

def rec(i, w):
	if dp[i][w] != -1:
		return dp[i][w]

	if i == 0:
		if w == 0:
			return True
		else:
			return False

	res = 0
	if w >= a[i - 1] and rec(i - 1, w - a[i - 1]) == 1:
		res = 1
	
	if rec(i - 1, w) == 1:
		res = 1

	dp[i][w] = res
	return dp[i][w]

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

dp = [[-1] * (2000 + 1) for _ in range(n + 1)]

for i in range(m):
	print('yes') if rec(n, q[i]) == 1 else print('no')

Submission status: Accepted

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

tar = max(max(m),sum(A))+1
dp = [[0]*tar for i in range(n+1)]
dp[0][0] = 1

for j in range(n):
    for k in range(tar):
        dp[j+1][k] = dp[j+1][k] or dp[j][k]

        if k >= A[j]:
            dp[j+1][k] = dp[j+1][k] or dp[j][k-A[j]]

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

Submission status: Accepted

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

q = int(input())
m = [int(i) for i in input().split()]

def dfs(idx, s, target):
    if s == target:
        return 1
    
    if s > target or idx == n:
        return 0
    if s + sum(A[idx:]) < target:
        return 0

    return dfs(idx+1, s, target) or dfs(idx+1, s + A[idx], target)

for target in m:
    ans = 'yes' if dfs(0, 0, target) else 'no'
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
q = int(input())
Q = list(map(int, input().split()))
 
bits = 1
for a in A:
    bits |= bits << a
 
for q in Q:
    if bits >> q & 1:
        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()))
flag = [0] * 2000
for i in range(2 ** len(a)):
         tmp = 0
         for j in range(len(a)):
                  if ((i >> j) & 1) == 1:
                           tmp += a[j]
         flag[tmp] = 1

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

Lis = set([])

for i in range(2**a):
    su = 0
    for j in range(n):
        if ((i >> j) & 1):
            su += A[j]
    Lis.add(su)

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    n_lis = []
    n_lis= list(map(int, input().split()))
    q = int(input())
    q_lis = []
    sum_lis = []
    q_lis = list(map(int, input().split()))
    
    for i in range(2**n):
        test_lis = []
        for j in range(n):
            if ((i>>j) & 1):
                test_lis.append(n_lis[j])
        sumtest = sum(test_lis)
        sum_lis.append(sumtest)
    for qs in q_lis:
        if qs in sum_lis:
            print("yes")
        else:
            print("no")

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import collections,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
n = I()
A = LI()
q = I()
m = LI()
partial_sum = set()
stack = [] #indexとsumを入れておく
def dfs():
    stack.append([0,0])
    stack.append([0,A[0]])
    partial_sum.add(A[0])
    while stack:
        i,s = stack.pop()
        i += 1
        if i==n:
            partial_sum.add(s)
            continue
        stack.append([i,s])
        stack.append([i,s+A[i]])
dfs()
for x in m:
    print('yes' if x in partial_sum else 'no')

Submission status: Accepted

Solution code:
n = int(input())
al = [int(i) for i in input().split()]
m = int(input())
bl = [int(i) for i in input().split()]


ans_set = set()
for i in range(1,1<<n):
    num = 0
    for j in range(n):
        if (i >> j) & 1:
            num += al[j]
    ans_set.add(num)
    
    
for i in bl:
    if i in ans_set:
        print('yes')
    else:
        print('no')

Submission status: Accepted

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

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

# bit全探索
pattern = set()
for i in range(2 ** n):
    ans = 0
    for j in range(n):
        if (i >> j) & 1:
            ans += num[j]
    pattern.add(ans)

for check in checks:
    if check in pattern:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

dp = []
def solve(i, m):
    if i == n:
        dp.append(m)
        return
    solve(i+1, m)
    solve(i+1, m+a[i])
solve(0, 0)

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

Submission status: Accepted

Solution code:
n=int(input())
a = tuple(map(int,input().split()))
dp = [0]*(n*max(a)+1)
dp[0] = 1
for i in range(n):
    past = list(dp)
    for m in range(n*max(a)+1):
        if m-a[i]>=0:
            dp[m] = max(dp[m],past[m-a[i]])
        else:
            dp[m] = past[m]
q = int(input())
for s in tuple(map(int,input().split())):
    if s > max(a)*n:
        print('no')
    elif dp[s]:
        print('yes')
    else:print('no')

Submission status: Accepted

Solution code:
from sys import stdin
N =list(map(int, stdin.readline().strip().split()))[0]
num_list=list(map(int, stdin.readline().strip().split()))
M=list(map(int, stdin.readline().strip().split()))[0]
ans_list=list(map(int, stdin.readline().strip().split()))
n=[]
def calc(i,ans):
    if i==N :
        return ans
    n.append(calc(i+1,ans))
    n.append((calc(i+1,ans+num_list[i])))
    return ans
calc(0,0)
n=list(set(n))
for an in ans_list:
    if an in n:print("yes")
    else:print("no")

Submission status: Accepted

Solution code:
from itertools import product

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

x = set([])
for bit in product([0, 1], repeat=n):
    cnt = 0
    for i, v in enumerate(bit):
        if v == 1:
            cnt += a[i]
    x.add(cnt)

for i in m:
    if i in x:
        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()))

MAX = 2000
check = [False] * MAX


def recursive(ind, tmp_sum):
  global n
  if ind == n:
    check[tmp_sum] = True
    return

  recursive(ind+1, tmp_sum)
  if tmp_sum + A[ind] <= MAX:
    recursive(ind+1, tmp_sum + A[ind])

recursive(0,0)

for num in m:
  if check[num]:
    print('yes')
  else:
    print('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()
for a in range(1,len(A)):
    for com in combinations(A,a):
        l.add(sum(com))
            
for m in M:
    if m in l:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
from functools import lru_cache

@lru_cache(maxsize=None)
def is_possible(n, target, total):
    if n == 0:
        return total == target
    return is_possible(n-1, target, total) or is_possible(n-1, target, total + A[n-1])


n = int(input())
A = [int(i) for i in input().split()]
_ = int(input())


for target in map(int, input().split()):
    print('yes' if is_possible(n, target, 0) else'no')

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces


def BinarySearch(num, nums):
    if len(nums) == 0:
        print("Erorr : list has no element")
        return
    left,right = 0,len(nums)
    while left < right:
        mid  = (left+right)//2
        if num < nums[mid]:
            right = mid
        else:
            left = mid + 1
    return right


def BitSearch(a):
    n = len(a)
    rets = []
    for i in range(pow(2,n)):
        ret = 0
        for j in range(n):
            if ((i>>j) & 1):
                ret += a[j]
        rets += [ret]
    return rets


def main():
    n = ni()
    a = na()
    aBitSum = sorted(BitSearch(a))
    qn = ni()
    qs = na()
    for q in qs:
        mid = BinarySearch(q,aBitSum)
        if aBitSum[mid-1] == q:
            print('yes')
        else:
            print('no')
    return


if __name__ == '__main__':
    main()