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:
def number_list(A):
    number_list = set()
    for bit in range(1 << len(A)):
        sum_a = 0
        for i in range(len(A)):
            if bit & (1 << i):
                sum_a += A[i]
                number_list.add(sum_a)
    return number_list


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

    number_list = number_list(A)

    for m in M:
        if m in number_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()))
# bit 全探索
# aから適当にとってm[i]にできるかをそれぞれ答える
# 1.aでできるパターンんお和をbit 全探索で探す
pat_sum = [0]*(2**n)
for i in range(2**n):
  wa = 0
  for j in range(n):
    if i >> j & 1:
      wa += a[j]
  pat_sum[i] = wa
pat_sum.sort()# sortするのを忘れてた
# 2. mをsortして、かつ答えるときのためにidxを保持しておく
m,idx = zip(*sorted(zip(m,range(q))))
# 3. while で回して、i,jを末端にいくまで添字をしたからずらして、matchするかを確かめる
a_idx = 0
m_idx = 0
# point ２つの配列を添字をずらしながら全探索するときはwhile a < len or b<lenとする
ans = [""]*q#sortした時の順番で入る
# 回す時の順番はpat_sumを回す
while a_idx < 2**n:#抜ける時が==n m_idx == qは抜けてからno 埋め
  if pat_sum[a_idx] > m[m_idx]: # 小さい方を添字上げる
    ans[idx[m_idx]] = "no"
    m_idx += 1
  elif pat_sum[a_idx] < m[m_idx]:
    a_idx += 1
  else:# = の時は、探索する方の添字を上げる in case same element in m
    ans[idx[m_idx]] = "yes"
    m_idx += 1
  if m_idx == q:
    break
# 同じelementが複数ある時にerror
# a_idx ==n とm_idx == qで条件分岐する
# while の時、添字+=1するのわすれガチ
while m_idx < q:
  ans[idx[m_idx]] = "no"
  m_idx += 1
# 4. idx　の順に出力
for i in range(q):
  print(ans[i])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))
pos = []
for i in range(2**n):
    a = 0
    for j in range(n):
        if ((i>>j)&1):
            a += A[j]
    pos.append(a)
for m in M:
    if m in pos:
        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 = [False] * 2000
for i in range(2 ** n):
    # 各数字を使うかどうかを0,1で表現
    S = 0
    for j in range(n):
        if ((i >> j) & 1):
            S += A[j]
    flag[S] = True

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

result = []
for i in range(n):
    nums = result[::]
    result.append(a[i])
    for n in nums:
        result.append(n + a[i])

for mi in m:
    ans = 'yes' if mi in result else 'no'
    print(ans)

Submission status: Accepted

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

can_consist_numbers = dict()
for mask in range(1 << n):
    total = 0
    for i, a in enumerate(A):
        if mask & (1<<i) >= 1:
            total += a
    can_consist_numbers[total] = True

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

Submission status: Accepted

Solution code:

def main():
    n = int(input())
    a = list(map(int,input().split()))
    m = int(input())
    q = list(map(int,input().split()))
    mem = [False]*40001
    def dfs(i,s):
        mem[s] = True
        if n<=i:return
        dfs(i+1,s)
        dfs(i+1,s+a[i])
    dfs(0,0)
    for i in q:
        if mem[i]:print ('yes')
        else     :print ('no')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def can_solve(i, m, n, A):
    if m == 0:
        can = True
        return can
    if i >= n:  # 全部探索おわの条件
        can = False
        return can
    if m < 0:  # 足しすぎて負になった時の終了条件
        can = False
        return can
    if sum(A[i:]) < m:  # 全部足しても足りないようなときの終了条件
        can = False
        return can

    can = can_solve(i+1, m, n, A) or can_solve(i+1, m-A[i], n, A)
    return can




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

    for mi in m:
        if can_solve(i=0,m=mi,n=n,A=A):
            print("yes")
        else:
            print("no")

Submission status: Accepted

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

ma = max(m)
dp = [[0] * (ma+1) for _ in range(n+1)]
for i in range(n):
    dp[i][0] = 1

for i in range(ma+1):
    for j in range(n):
        if i - a[j] < 0:
            dp[j+1][i] = dp[j][i]
            continue
        else:
            dp[j+1][i] = max( dp[j][i] , dp[j][i - a[j]] )
            
for i in m:
    if dp[n][i] == 1:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
import copy
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
M=list(map(int,input().split()))
dp=list()
S=sum(A)
dp.append([1]+[0]*S)
for i in range(N):
  dp.append(copy.copy(dp[-1]))
  for j in range(S-A[i]):
    dp[i+1][j+A[i]]=dp[i+1][j+A[i]]+dp[i][j]
L=list()
for i in range(N+1):
  for j in range(len(dp[i])):
    if dp[i][j]!=0:
      L.append(j)
L=set(L)
for i in range(Q):
  if M[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()))

R=[]

for i in range(1<<n):
    r=0
    for j in range(n):
        if i&(1<<j):
            r+=A[j]
    R.append(r)

R=set(R)

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

Submission status: Accepted

Solution code:
def inpl():
    return tuple(map(int, input().split()))


def getHash():
    def value(i):
        ret = 0
        for j in range(N):
            if (i >> j) % 2:
                ret += A[j]
        return ret
    return set(value(i) for i in range(2**N))


def solve(m):
    return "yes" if m in hash else "no"


N = int(input())
A = inpl()

Q = int(input())
M = inpl()

hash = getHash()

for m in M:
    print(solve(m))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
capa = []
for i in range(2**n):
    s = 0
    num = [0] * n
    for j in range(n):
        if (i>>j)&1:
            num[n-j-1] = 1
    for i in range(n):
        if num[i] == 1:
            s += a[i]
    capa.append(s)
for i in m:
    if i in capa:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
from collections import defaultdict
def main(n,a):
    for i in range(2**n):
        ans=0
        for j in range(n):

            if (i>>j)&1:
                ans+=a[j]
        cnt[ans]=1
cnt = defaultdict(lambda: 0)
n=int(input())
a=list(map(int,input().split()))
main(n,a)
q=int(input())

for i in list(map(int,input().split())):
    if cnt[i]==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()))

V = []

for i in range(1<<n):
    b = format(i, '0%db'%n)
    k = 0
    for j, bb in enumerate(b):
        if bb == '1':
            k += A[j]
    V.append(k)

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

sum_A = set()
for i in range(N):
    for cmb in combinations(A, i+1):
        sum_A.add(sum(cmb))

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

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
_=int(input())
Q=list(map(int,input().split()))

ansl=[0 for i in range(2002)]

for bit in range(1<<n):
    ans=0
    for v in range(n):
        if bit>>v & 1:
            ans+=A[v]
    ansl[ans]=1

for i in Q:
    print("yes" if ansl[i] else "no")

Submission status: Accepted

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

ubd = 2000

table = [False] * (ubd + 5)
S = [0] * n


def enum(i):
    global table
    if i == n:
        sum = 0
        for j in range(n):
            sum += li_in[j] * S[j]
        if sum <= 2000:
            table[sum] = True
    else:
        enum(i + 1)
        S[i] = 1
        enum(i + 1)
        S[i] = 0


enum(0)

for val in li_check:
    if table[val]:
        print('yes')
    else:
        print('no')


# 失敗作: 毎回再帰で計算
# 各回，数が一つくるごとに全探索している．
# 時間がかかりすぎる．最初に可能な数を全て計算した上でストックし，それを各数に対して用いれば良い．

# S = [0] * n
# flag = False


# def enum(i, val):
#     global flag
#     if i == n:
#         sum = 0
#         for j in range(n):
#             sum += li_in[j] * S[j]
#         if sum == val:
#             flag = True
#     else:
#         enum(i + 1, val)
#         S[i] = 1
#         enum(i + 1, val)
#         S[i] = 0


# for val in li_check:
#     flag = 0
#     enum(0, val)
#     if flag:
#         print('yes')
#     else:
#         print('no')

Submission status: Accepted

Solution code:
import sys,collections
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
q = int(sys.stdin.readline())
m = list(map(int,sys.stdin.readline().split()))
def isOK(rest,i):
  if rest == 0:
    return True
  if i == n or rest < 0:
    return False
  if sum(a[i:]) < rest:
    return False
  if isOK(rest-a[i],i+1):
    return True
  return isOK(rest,i+1)
for mi in m:
  if isOK(mi,0):
    print("yes")
  else:
    print("no")

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:
def main():
    n=int(input())
    a=list(map(int,input().split()))
    m=int(input())
    q=list(map(int,input().split()))
    
    ans=[None]*m
    
    for i in range(2**n):
        total=0
        for j in range(n):
            if ((i>>j)&1):
                total+=a[j]
        for i in range(m):
            if q[i]==total:
                ans[i]=True
    for i in ans:
        if i==True:
            print('yes')
        else:
            print("no")

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from functools import lru_cache


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


@lru_cache(maxsize=2**12)
def solve(i, m):
    if m == 0:
        return True
    if i >= n:
        return False
    ans = solve(i + 1, m) or solve(i + 1, m - A[i])
    return ans


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

Submission status: Accepted

Solution code:
def solve(total, idx):
    if total > 2000:
        return
    can_make[total] = True
    if idx == n:
        return
    solve(total + A[idx], idx + 1)
    solve(total, idx + 1)


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

can_make = [False] * (2000 + 1)
solve(0, 0)

M = int(input())
Q = [int(x) for x in input().split()]
for q in Q:
    print('yes' if can_make[q] else 'no')

Submission status: Accepted

Solution code:
n = int(input())
aa = tuple(map(int, input().split()))
q = int(input())
mm = tuple(map(int, input().split()))

possible_m = set()
for bit in range(1 << n):
    total = 0
    for i, a in enumerate(aa):
        if (bit >> i) & 1:
            total += a
    possible_m.add(total)
for m in mm:
    if m in possible_m:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
def createTable(a):
    n = len(a)
    table = set()
    for i in range(1 << n):
        array = []
        for j in range(n):
            if (i & 1 << j) > 0:
                array.append(a[j])
        table.add(sum(array))
    return table


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

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

table = createTable(a)

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

Submission status: Accepted

Solution code:
import sys
import bisect
stdin = sys.stdin

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

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

    return res
for mi in m:
    if solve(0, mi):
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from itertools import combinations
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    n=int(input())
    A=list(map(int,input().split()))
    s=set()
    for i in range(2**n):
        tmp=0
        for j in range(n):
            if (i>>j)&1:
                tmp+=A[j]
        s.add(tmp)
    q=int(input())
    m=list(map(int,input().split()))
    for x in m:
        print('yes' if x in s else 'no')
        


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect

n = int(input())
A = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
slst = []
slen = 0
for i in range(2 ** n):
    total = 0
    for j in range(n):
        if i >> j & 1:
            total += A[j]
    slst.append(total)
slst.sort()
slen = 2 ** n
for i in range(q):
    tmp = bisect.bisect_left(slst, m[i])
    if tmp != slen and m[i] == slst[tmp]:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
from itertools import combinations
import bisect
n = int(input())
*A, = map(int, input().split())
q = int(input())
*M, = map(int, input().split())
S = set()
for i in range(1, n + 1):
    for c in combinations(A, i):
        S.add(sum(c))
for m in M:
    if m in S:
        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()]
cand = set()
l_A = len(A)

for i in range(2**l_A):
    guess = 0
    for j in range(l_A):
        if(i>>j & 1 == 1):
            guess += A[j]
    cand.add(guess)

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

Submission status: Accepted

Solution code:
#Exhaustive Search
N=int(input())
A=list(map(int,input().split()))

bit_all=[]
for i in range(2**N):
    bit=[]
    for _ in range(N):
        bit.append(i%2)
        i//=2
    bit_all.append(bit)

m_list=[]
for bit in bit_all:
    m=0
    for a,b in zip (A,bit):
        m+=a*b
    m_list.append(m)

M=int(input())
q=list(map(int,input().split()))
for i in range(M):
    if q[i] in m_list:
        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:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    q = I()
    m = LI()
    M = max(m)
    l = [i for i in a[:n>>1]]
    r = [i for i in a[n>>1:]]
    nl = len(l)
    nr = len(r)
    fl = [0]*(M+1)
    fr = [0]*(M+1)
    for b in range(1<<nl):
        s = 0
        for i in range(nl):
            if b&(1<<i):
                s += l[i]
        if s <= M:
            fl[s] = 1
    for b in range(1<<nr):
        s = 0
        for i in range(nr):
            if b&(1<<i):
                s += r[i]
        if s <= M:
            fr[s] = 1
    f = [0]*(M+1)
    for i in range(M+1):
        if not fl[i]:
            continue
        for j in range(M+1-i):
            if fr[j]:
                f[i+j] = 1
    for i in m:
        print(["no","yes"][f[i]])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n = int(input())
a = [i for i in map(int, input().split())]
q = int(input())
m = [i for i in map(int, input().split())]

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

for target in m:
    if sum(a) < target:
        print('no')
    elif solve(0, target):
        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 = set()
for i in range(2**n):
    tmp = 0
    for j in range(n):
        if i >> j & 1:
            tmp += A[j]
    s.add(tmp)
for i in range(q):
    if M[i] in s:
        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()]

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

ans = set(ans)

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

Submission status: Accepted

Solution code:
N = int(input())
num_list = [int(item) for item in input().split()]
q = int(input())
q_list = [int(item) for item in input().split()]


deque = []
for i in range(1,2**N):
    temp_num = 0
    for j in range(N):
        if (i >> j) & 1 == 1:
            temp_num += num_list[j]
    deque.append(temp_num)

# res_list = list(deque)
for k in q_list:
    if k in deque:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
import copy
n = int(input())
can = [0 for i in range(2001)]
can[0]=1

A = list(map(int,input().split()))
q = int(input())
Q = list(map(int,input().split()))
for i in range(len(A)):
    #can2 = [0 for i in range(2001)]
    #for j in range(len(can)):
        #can2[j]=can[j]
    can2 = copy.copy(can)
    for j in range(A[i],len(can)):
        can2[j] = max(can[j],can[j-A[i]])
    can = can2
    

for i in range(q):
    if can[Q[i]]==1:print('yes')
    else:print('no')

Submission status: Accepted

Solution code:
import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

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

ans = [False] * Q
for bit in range(1 << N):
    acc = 0
    for i in range(N):
        if (bit & (1 << i)):
            acc += A[i]
    if acc in M:
        for i, m in enumerate(M):
            if acc == m:
                ans[i] = 1

for a in ans:
    if a:
        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()))
M=2000
table=[0 for _ in range(M+1)]

def solve(i,m):
    if i==n:
        table[m]=1
        return 
    solve(i+1,m)
    if m+A[i]<=M:
        solve(i+1,m+A[i])

solve(0,0)

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

Submission status: Accepted

Solution code:
def search_dfs(A, n):
    def __inner(i, sum_v, goal):
        if sum_v == goal:
            return True
        if sum_v > goal or i >= n:
            return False
        if sum_v + sum(A[i:]) < goal:
            return False
            
        return __inner(i+1, sum_v, goal) or __inner(i+1, sum_v+A[i], goal)
    
    return __inner


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

dfs = search_dfs(A, n)

for goal in M:
    print('yes') if dfs(0, 0, goal) 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 or m < 0:
    return False
  if sum(A[i:]) < m:
    return False
  res =  solve(i+1, m) or solve(i+1, m-A[i])
  return res

ans = [solve(0,m) for m in M]
for a in ans:
  print('yes') if a 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 = set()

for bit in range(1 << n):
    s = 0
    for i in range(n):
        s += A[i] * (bit & (1 << i) > 0)
    ans.add(s)

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=tuple(map(int,input().split()))
    q=int(input())
    ms=tuple(map(int,input().split()))
    
    make=set()
    for bit in range(1<<n):
        num=0
        for j in range(n):
            if (bit>>j)&1:
                num+=a[j]
        make.add(num)
    
    for m in ms:
        if m in make:
            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()))
ans = set()
for i in range(1, (1 << N)):
    tmp = 0
    for j in range(0, N):
        if (i >> j) & 1:
            tmp += A[j]
    ans.add(tmp)
for m in M:
    if m in ans:
        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 can_make(t, d):
    if t==0:
        return True
    elif t<0 or t>sum(a[d:]):
        return False
    elif d==n:
        return False
    elif can_make(t-a[d], d+1) or can_make(t, d+1):
        return True
    else:
        return False
        
for i in range(q):
    if can_make(m[i], 0):
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
import bisect
import itertools

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

for m in M:
    if m in A:
        print("yes")
    elif sum(A) < m:
        print("no")
    else:
        # mよりも小さいAの要素のみを対象
        index = bisect.bisect_left(A, m)
        tgtA = A[:index]
        
        num = len(tgtA)
        judge = False
        while num > 0:
            combList = list(itertools.combinations(A, num))
            for comb in combList:
                if m == sum(comb):
                    judge = True
                    break

            if judge:
                break

            num -= 1

        if judge:
            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()))
q=int(input())
m=list(map(int,input().split()))

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

Submission status: Accepted

Solution code:
def exhaustive(index, end, target, table):
    if end == target:
        return True
    if end > target or index == n:
        return False
    if end + sum(table[index:]) < target:
        return False
    return exhaustive(index+1, end, target, table) or exhaustive(index+1, end+table[index], target, table)

if __name__ == "__main__":
    n = int(input())
    table = list(map(int, input().split()))
    q = int(input())
    m = list(map(int, input().split()))
    for i in m:
        if exhaustive(0, 0, i, table):
            print("yes")
        else:
            print("no")

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
nq = int(input())
Q = list(map(int, input().split()))
m = 2 ** n
A_s = set()
for i in range(m):
    b = list(map(int, str(bin(i))[2:].zfill(n)))
    s = 0
    for j in range(n):
        s += A[j] * b[j]
    A_s.add(s)
for q in Q:
    if q in A_s:
        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()]
flag=[0]*2000

for m in range(1<<N):
    n=0
    for i in range(N):
        if 1&(m>>i)==1:
            n+=A[i]
    flag[n]=1

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

F = "{:0" + str(n) + "b}"
variations = set()
for i in range(2 ** n):
    b = F.format(i)
    s = 0
    for j, bj in enumerate(b):
        if bj == "1":
            s += A[j]
    variations.add(s)

for query in m:
    if query in variations:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
q = list(map(int, input().split()))
dp = [[False]*2001 for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = True
for i in range(n):
    for j in range(2001):
        if j+a[i] <= 2000:
            dp[i+1][j+a[i]] = dp[i+1][j+a[i]] | dp[i][j]
        dp[i+1][j] = dp[i][j] | dp[i+1][j]
for query in q:
    if dp[n][query]:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
N=int(input())
n_list=list(map(int,input().split(' ')))
M=int(input())
q = list(map(int,input().split(' ')))
ans = []
for i in range(2**N):
    str_bin = format(i,'0{}b'.format(N))
    tmp = 0
    for n,j in enumerate(str_bin):
        if j=='1':
           tmp += n_list[n]
    ans.append(tmp)
ans = set(ans)
for i in q:
    if i in ans:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
import collections
n=int(input())
arr=list(map(int,input().split()))
q=int(input())
arr2=list(map(int,input().split()))
dic=collections.defaultdict(int)
for i in range(2**n):
  tmp=0
  pos=0
  while i!=0:
    if i%2==1:
      i-=1
      tmp+=arr[pos]
    i=i//2
    pos+=1
  dic[tmp]+=1
for i in range(q):
  if dic[arr2[i]]!=0:
    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(" ")))
results = []

for i in range(2**n):
    sum = 0
    for keta in range(n):
        # i >> 2 で10進数表記のnを2進数変換して2けたぶん右にシフトしてくれる。
        # 結果2け為の1, 0 がわかる
        if (i >> keta) & 1:
            sum += A[keta]
    results.append(sum)

results = set(results)
for target in M:
    print('yes') if target in results 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()]
ans=[False]*q
c=[[] for i in range(2001)]
for i in range(q):
    c[m[i]].append(i)


for i in range(1<<n):
    b=bin(i)[2:].rjust(n,"0")
    tmp=0
    for j in range(n):
        if int(b[j]):
            tmp+=a[j]
    for j in c[tmp]:
        ans[j]=True

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

def main():
    n = int(input().strip())
    a = list(map(int, input().strip().split()))
    q = int(input().strip())
    m = list(map(int, input().strip().split()))
    l = []
    for i in range(2**n):
        w = 0
        for j in range(n):
            if 1 & (i >> j) == 1:
                w += a[j]
        l.append(w)
    l = set(l)
    for i in range(q):
        if m[i] in l:
            print('yes')
        else:
            print('no')
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
import itertools
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

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

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

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
q = list(map(int, input().split()))

flg = [0 for _ in range(2001)]

for i in range(2**N):
	out = 0
	for j in range(N):
		if i & (1 << j):
			out += A[j]

	if out <= 2000:
		flg[out] = 1

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