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:
import sys, os, math \
    # , bisect, itertools, collections, heapq, queue

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque
# import copy

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    Q = ii()
    M = il()

    num_set = set()
    for i in range(1 << N):
        num = 0
        for n in range(N):
            if i >> n & 1:
                num += A[n]
        num_set.add(num)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

N = int(input())
table = list(map(int,input().split()))

MAX = 2000
check = [False]*(MAX+1)

def recursive(index,tmp_sum):
    global N

    if index == N:
        check[tmp_sum] = True
        return

    recursive(index+1,tmp_sum)
    if tmp_sum+table[index] <= MAX:
        recursive(index+1,tmp_sum+table[index])

recursive(0,0)

num_query = int(input())
for num in list(map(int,input().split())):
    if check[num]:
        print("yes")
    else:
        print("no")

Submission status: Accepted

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

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

ans = [0]*q
tmp_li = []

for i in range(2**n):
    check = [0]*n
    
    for j in range(n):
        if ((i >> j) & 1):
            check[n - 1 - j] = 1
    
    tmp = 0
    for a in range(n):
        if check[a] == 1:
            tmp += n_li[a]
    tmp_li.append(tmp)

for k in range(q):
    if q_li[k] in tmp_li:
        ans[k] = 1
        
for x in ans:
    if x == 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()))

sumlist=[]

for i in range(2**n):
    sumA=0
    for j in range(n):
        if ((i>>j) & 1):
            sumA+=A[j]
    sumlist.append(sumA)

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

Submission status: Accepted

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

st=set()
for i in range(1<<n):
  sm=0
  for j in range(n):
    if (i & (1<<j)):
      sm+=a[j]
  st.add(sm)
Q=list(map(int,input().split()))
for i in Q:
  if i in st:
    print("yes")
  else:
    print("no")

Submission status: Accepted

Solution code:
from typing import List


def rec(i: int, tmp_sum: int, A_list: List[int], sum_list: List[bool]):
    if tmp_sum > 2000:
        return
    elif i == len(A_list):
        sum_list[tmp_sum] = True
        return

    rec(i + 1, tmp_sum + A_list[i], A_list, sum_list)
    rec(i + 1, tmp_sum, A_list, sum_list)


def main():
    n = int(input())
    A_list = list(map(int, input().split()))
    q = int(input())
    m_list = list(map(int, input().split()))

    sum_list = [False for _ in range(2001)]

    rec(0, 0, A_list, sum_list)

    for m in m_list:
        if sum_list[m]:
            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()))

cand = []
for i in range(2**n):
    tmp = 0
    for j in range(n):
        if (i>>j)&1:
            tmp += A[j]
    cand.append(tmp)

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

Submission status: Accepted

Solution code:
import sys
from itertools import product


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    q = int(input())
    m = list(map(int, input().split()))
    ans = [False] * q
    for e in product((0, 1), repeat=n):
        s = 0
        for i in range(n):
            s += e[i] * a[i]
        for i in range(q):
            if m[i] == s:
                ans[i] = True
    for a in ans:
        print("yes" if a else "no")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
se = set()
for i in range(1<<N):
    tot = 0
    for j in range(N):
        if i&(1<<j): tot += A[j]
    se.add(tot)
_ = int(input())
Q = list(map(int, input().split()))
for q in Q:
    if q in se:
        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()))

A = [0]*(2**n)
c = 0
for x in product([0,1], repeat=n):
    summ = 0
    for j in range(n):
        if x[j] == 1:
            summ += a[j]
    A[c] = summ
    c+=1

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

Submission status: Accepted

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

ans = ["no"]*2000

for i in range(1<<n):
    a = 0
    for j in range(n):
        if (i>>j)&1 == 1:
            a += A[j]
    ans[a] = "yes"

for j in M:
    print(ans[j])

Submission status: Accepted

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

Submission status: Accepted

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

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

comb = set()

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

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

Submission status: Accepted

Solution code:
n = int(input())
(*a, ) = map(int, input().split())
q = int(input())
(*m, ) = map(int, input().split())
s = set()
for j in range(2 << n):
    c = 0
    for k in range(n):
        if j >> k & 1:
            c += a[k]
    s.add(c)

for i in m:
    print("yneos"[i not in s::2])

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
q=int(input())
m=list(map(int,input().split()))
b=[0]*2**n
for i in range(2**n):
  tr=bin(i)[2:].zfill(n)
  cnt=0
  for j in range(n):
    if tr[j]=='1':
      cnt+=a[j]
  b[i]=cnt
for i in m:
  if i in b:print('yes')
  else:print('no')

Submission status: Accepted

Solution code:
N=int(input())
L=list(map(int,input().split()))
B=1
for i in range(N):
    B=B|B<<L[i]
BI=list(str(bin(B)))
BI=BI[2:]
SB=BI[::-1]
#print(SB)
Q=int(input())
A=list(map(int,input().split()))
for i in range(Q):
    if A[i]>=len(SB):
        print("no")
    elif SB[A[i]]=="1":
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
import sys
from itertools import product

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    num = set()
    for pattern in product([0, 1], repeat=n):
        total = 0
        for idx, p in enumerate(pattern):
            if p == 1:
                total += A[idx]
        num.add(total)

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

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


for j in q:
  if j in S:
    print("yes")
  else:
    print("no")

Submission status: Accepted

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

result = set()
for i in range(2**n):
    tmp = 0
    for j in range(n):
        if i >> j & 1:
            tmp += arr[j]
    result.add(tmp)

for x in m:
    print("yes" if x in result else "no")

Submission status: Accepted

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

    sum_list = []
    back = []
    #bit全探索
    for i in range(1,2**n):
        for j in range(n):
            if ( (i>>j)&1 ):
                back.append(A[j])

        #print(back)

        sum = 0
        for k in back:
            sum += k

        sum_list.append(sum)

        back = []

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

main()

Submission status: Accepted

Solution code:
N = int(input().rstrip())
A = [int(_) for _ in input().rstrip().split(" ")]
Q = int(input().rstrip())
M = [int(_) for _ in input().rstrip().split(" ")]

import itertools

from functools import lru_cache

@lru_cache(maxsize=2**12)
def solve(i, m):
    if m == 0:
        return True
    elif 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:
from itertools import combinations as comb

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

numlst=[]
for i in range(1,n+1):
    for x in comb(lst,i):
        y=sum(x)
        if not y in numlst:
            numlst.append(y)

q=int(input())
lst2=list(map(int,input().split()))
for x in lst2:
    if x in numlst : 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()))

# bit all search
pattern = []
for i in range(2 ** n):
    bit_set = []
    for j in range(n):
        if ((i >> j) & 1):
            bit_set.append(A[j])    
    pattern.append(sum(bit_set))

#print(pattern)  

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

cand_list = []
for i in range(1, 2**n):
    cum_num=0
    for j in range(n):
        if i&1<<j:
            cum_num += A[j]
    cand_list.append(cum_num)
    
for m in M:
    if m in set(cand_list):
        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+1)
for status in range(2**n):
    tmp = 0
    for mask in range(n):
        if status&(1<<mask):
            tmp += A[mask]
    flag[tmp] = True

for m in M:
    print('yes' if flag[m] 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()))

k = 2**N
totallist = [0]*k
for b in range(k):
    total = 0
    for i in range(N):
        if b >> i & 1 == 1:
            total += A[i]
    totallist[b] = total

for m in M:
    print('yes') if m in totallist 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()))
mans = set()
b = 0
for b in range(2**n):
    ans = 0
    for i in range(n):
        if 1&(b>>i):
            ans += A[i]
    mans.add(ans)
for m in M:
    if m in mans:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
def resolve():
    n=int(input())
    a=list(map(int,input().split()))
    q=int(input())
    m=list(map(int,input().split()))
    sa=[0]*100000
    for i in range(2**n):
        s=0
        for j in range(n):
            if i>>j&1:
                s+=a[j]
        sa[s]=1
    for i in m:
        if sa[i]==0:
            print('no')
        else:
            print('yes')

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

ans = set()
for i in range(2**n):
    total = 0
    bits = bin(i)[2:].zfill(n)
    for j, b in enumerate(bits):
        if b == '1':
            total += A[j]
    ans.add(total)

for i in range(q):
    if M[i] in ans:
        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()))
SL = []
for bit in range(1<<N):
    SUM = 0
    for i in range(N):
        if bit & (1<<i):
            SUM += A[i]
    SL.append(SUM)
for q in Q:
    if q in SL:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
N=int(input())
U=list(map(int,input().split()))
M=int(input())
T=list(map(int,input().split()))

#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
dp = [[-1 for j in range(400001)] for i in range(N+1)]


def func(i,X,U,dp):
    if i==0:
        if X==0:
            return True
        else:
            return False
    if X<0:
        return False
    
    if dp[i][X] !=-1:
        return dp[i][X]
    
    
    if func(i-1,X,U,dp):
        dp[i][X]=1
        return dp[i][X]
    if (func(i-1,X-U[i-1],U,dp)):
        dp[i][X]=1
        return dp[i][X]
    
    dp[i][X]=0
    return dp[i][X]

for i in range(M):
    if func(N,T[i],U,dp)==True:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

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

Submission status: Accepted

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

# n桁分のbit探索
for i in range(1 << n):
    point = 0
    for j in range(n):
        # j個目の商品が含まれるか
        if (i >> j)&1:
            point += a[j]
    pos.add(point)

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

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

Submission status: Accepted

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

n = int(stdin.readline().rstrip())
A = list(map(int,stdin.readline().split()))
q = stdin.readline().rstrip()
M = list(map(int, stdin.readline().split()))

sum_results = set()

for i in range(2 ** n):
  sum_tmp = 0
  for j in range(n):
    # print("pattern i:{} j:{} i>>j{}".format(i,j,i>>j))

    if ((i >> j) & 1):  #順に右にシフトさせ最下位bitのチェックを行う
      sum_tmp += A[j]
  else:
    sum_results.add(sum_tmp)

for m in M:
  if m in sum_results:
    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()))

ans = [0] * (2 ** n)
for i in range(2 ** n):
    p = 1
    for j in range(n):
        if i & p:
            ans[i] += A[j]
        p *= 2

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

Submission status: Accepted

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

A_sum = []
for bit in range(1,2**n):
    a_sum = 0
    for i in range(n):
        if bin((bit>>i) & 0b1) == '0b1':
            a_sum += A[i]
    A_sum.append(a_sum)
            
for mi in m:
    if mi in A_sum:
        print('yes')
    else:
        print('no')

Submission status: Accepted

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

li = []
for i in range(2**n):
    an = format(i, 'b').zfill(n)
    li.append(an)

ans = []
for lis in li:
    num = 0
    for i in range(n):
        if lis[i] == '1':
            num += nums[i]
    ans.append(num)

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

Submission status: Accepted

Solution code:
from sys import stdin

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

def solve(i,m):
    '''
    i番目以降の要素を使用してmを作れる場合、trueを返す
    '''
    if m == 0:
        return True
    if sum(A[i:]) < m:
        return False
    if i >= n:
        return False
    res = solve(i+1,m) or solve(i+1,m-A[i])
    return res

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

Submission status: Accepted

Solution code:
def part_sum(a,A):
    #初期化
    N=len(a)
    dp=[[-1 for i in range(A+1)] for j in range(N+1)]
    dp[0][0]=[]
    #DP
    for i in range(N):
        for j in range(A+1):
            if a[i]<=j: #i+1番目の数字a[i]を足せるかも
                if dp[i][j] != -1:
                    dp[i+1][j] = dp[i][j]
                elif dp[i][j-a[i]] != -1:
                    dp[i+1][j] = dp[i][j-a[i]]+[a[i]]
            else: #入る可能性はない
                dp[i+1][j]=dp[i][j]
    #生成可能な自然数の配列(辞書型)
    """
    num_list = {}
    for i in dp:
        for num,j in enumerate(i):
            if j != -1:
                num_list[num] = j
    return num_list
    """
    return dp[N][A]
a = int(input())
num = list(map(int,input().split()))
q = int(input())
ans = list(map(int,input().split()))
for i in ans:
    check = part_sum(num,i)
    #print(check)
    if check == -1:
        print("no")
    else:
        print("yes")

Submission status: Accepted

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

    res = list()

    def mul(a, b):
        return a * b

#   # bit探索
    # for i in range(2**n):
    #     x = [0] * n
    #     for j in range(n):
    #         if(i >> j) & 1:
    #             x[j] = 1
    #     res.append(sum(list(map(mul, a, x))))
    # for i in m:
    #     if i in res:
    #         print('yes')
    #     else:
    #         print('no')
#   # 再帰
    def dfs(A):
        # 終端条件 --- nループまで回したら処理して打ち切り
        if len(A) == n:
            # print(A)
            res.append(sum(list(map(mul, a, A))))
            return
        for v in range(2):
            A.append(v)
            dfs(A)
            A.pop()
    dfs([])
    for i in m:
        if i in res:
            print('yes')
        else:
            print('no')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    A = [int(i) for i in input().split()]
    ans = [False] * 2001
    for i in range(2**n):
        sumA = 0
        for j in range(n):
            if (i >> j) & 1:
                sumA += A[j]
        ans[sumA] = True
    q = int(input())
    M = [int(i) for i in input().split()]
    for m in M:
        if ans[m]:
            print("yes")
        else:
            print("no")


resolve()

Submission status: Accepted

Solution code:
def solve(n,A):
    x=pow(2,n)
    dp=[False]*2001
    for i in range(x):
        count=0
        for j in range(n):
            if (i>>j)&1:
                count+=A[j]
        if count<=2000:
            dp[count]=True
    return dp

n=int(input())
A=list(map(int,input().split()))
q=int(input())
m=list(map(int,input().split()))
ans=solve(n,A)
for i in range(q):
    if ans[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()]

ok = [[0 for i in range(2001)] for j in range(21)]
ok[0][0] = 1

for i in range(n):
    for j in range(2001):
        if j+a[i] > 2000:
            ok[i+1][j] = max(ok[i][j], ok[i+1][j])
        else:
            ok[i+1][j] = max(ok[i][j], ok[i+1][j])
            ok[i+1][j+a[i]] = max(ok[i][j], ok[i+1][j+a[i]])

for i in m:
    print('yes' if ok[n][i] else 'no')

Submission status: Accepted

Solution code:
def main():
    import sys, itertools as ite
    n = int(sys.stdin.readline())
    A = tuple(map(int, sys.stdin.readline().split()))
    #print(A)
    q = int(sys.stdin.readline())
    M = map(int, sys.stdin.readline().split())
    bit = ite.product([0,1], repeat=n)
    ans = []
    for b in bit:
        tmp = 0
        for i in range(n):
            tmp +=b[i]*A[i]
        ans += [tmp]
        
    for m in M:
        if m in ans:
            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()))

for x in M:
  dp = [[0 for _ in range(x+1)] for _ in range(n+1)]
  dp[0][0]=1
  for i in range(n):
    for j in range(x+1):
      if A[i] <= j:
        dp[i+1][j] = dp[i][j - A[i]] or dp[i][j]
      else:
        dp[i+1][j] = dp[i][j]

  if dp[n][x] == 1:
    print ('yes')
  else:
    print ('no')

Submission status: Accepted

Solution code:
import sys

n = int(sys.stdin.readline())
A = [int(x) for x in sys.stdin.readline().split()]
q = int(sys.stdin.readline())
Qs = [int(x) for x in sys.stdin.readline().split()]

l = len(A)
N = 2000
dp = [False] * (N+1)
dp[0] = True

for a in A:
    tmp = dp.copy()
    for j in range(N+1):
        if j + a > N:break

        if tmp[j]:
            dp[j+a] = True

for m in Qs:
    if dp[m]:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

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

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

dp = [[None for i in range(max(M)+1)] for j in range(n+1)]

for m in M:    
    if solve(dp, n,A, 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 make_list(A):
    n = len(A)
    result = []
    for i in range(2**n):
        tmp = 0
        if i == 0:
            idx = ['0' for _ in range(n)]
        else:
            idx = list(bin(i).lstrip('0b').zfill(n))
        for num, j in enumerate(idx):
            if j == '1':
                tmp += A[num]
        result.append(tmp)
    return result


res = make_list(A)
for i in m:
    if i in res:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
def solve(n, A, q, m):
    memo = dict()
    for i in range(2**n):
        tmp = 0
        for j in range(n):
            if i >> j & 1:
                tmp += A[j]
        memo[tmp] = 1

    for val in m:
        print("yes" if val in memo else "no")

if __name__ == "__main__":
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    m = list(map(int, input().split()))
    solve(n, A, q, m)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
q=int(input())
m=list(map(int,input().split()))
l=[]
for i in range(2**n):
    sub=0
    for j in range(n):
        if (i>>j)&1==1:
            sub+=a[j]
    l.append(sub)
for i in m:
    if i in l:
        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()))
T = set()
for i in range(1, 2 ** n):
    total = 0
    for j in range(n):
        if i >> j & 1:
            total += A[j]
    T.add(total)
for m in M:
    if m in T:
        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 dfs(i,m):
    global a
    if i == 0:
        if m == 0:
            return True
        else:
            return False
    if dfs(i-1, m):
        return True
    if dfs(i-1,m - a[i-1]): 
        return True
    return False
for i in range(q):
    if dfs(n,m[i]):
        print("yes")
    else:
        print("no")"""
b = []
def dfs(i,m):
    global b
    if i == 0:
        b.append(m)
    else:
        dfs(i-1,m)
        dfs(i-1,m+a[i-1])
    return b
b = dfs(n,0)
for i in range(q):
    if m[i] in b:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
from sys import stdin

input = stdin.readline

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

set_m = set([])

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

    set_m.add(tmp)

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