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:
# -*- coding:utf-8 -*-

def solve():
    N = int(input())
    As = list(map(int, input().split()))
    q = int(input())
    Ms = list(map(int, input().split()))

    ans_set = set()
    for bit in range(0, 2**N):
        """bit全探索
        計算量はO(2**N) = O(1048576)
        """
        total = 0
        for i in range(N):
            total += As[i]*(bit>>i&1)

        ans_set.add(total)


    for m in Ms:
        if m in ans_set:
            print("yes")
        else:
            print("no")


def solve2():
    N = int(input())
    As = list(map(int, input().split()))
    q = int(input())
    Ms = list(map(int, input().split()))

    # dp[i][j] := i個まで使って、jを作れるかどうか
    dp = [[False for _ in range(N*2000+1)] for __ in range(N+1)]
    for i in range(N+1):
        dp[i][0] = True

    """dpを使って解く。
    計算量はO(N* N * 2000) = O(400 * 2000) = O(800000)
    """

    for i in range(1, N+1):
        for j in range(N*2000+1):
            if dp[i-1][j]:
                dp[i][j] = True
            if j+As[i-1] <= N*2000:
                dp[i][j+As[i-1]] = dp[i-1][j]

    ans_set = set()
    for j in range(N*2000+1):
        if dp[N][j]:
            ans_set.add(j)

    for m in Ms:
        if m in ans_set:
            print("yes")
        else:
            print("no")



if __name__ == "__main__":
    solve2()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
possible = set()
for i in range(2 ** n):
    tmp = 0
    for j in range(n):
        if (i >> j) & 1:
            tmp += a[j]
    possible.add(tmp)

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

made_num = list()
for i in range(1, 2**n):
    total = 0
    i_tmp = i
    for j in range(n):
        if i_tmp % 2 == 1:
            total += A[j]
        i_tmp //= 2
    made_num.append(total)

made_num_set = set(tuple(made_num))
for k in range(q):
    if m[k] in made_num_set:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
cin = open(0).read().split('\n')

n = int(cin[0])
a = list(map(int, cin[1].split(' ')))
q = int(cin[2])
m = list(map(int, cin[3].split(' ')))

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

for mi in m:
    if mi in tmp:
        print('yes')
    else:
        print('no')

Submission status: Accepted

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

memo=[[None]*(n+1) for _ in range(max(m)+1)]

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


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

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int, input().split()))
L, R = {0}, {0}
for i in range(len(arr)//2):
    tmp = {arr[i]}
    for a in L:
        tmp.add(a + arr[i])
    L |= tmp
for i in range(len(arr)//2, len(arr)):
    tmp = {arr[i]}
    for a in R:
        tmp.add(a + arr[i])
    R |= tmp
input()
for m in map(int, input().split()):
    tag = False
    for a in L:
        if m - a in R:
            tag = True
            break
    print(['no', 'yes'][tag])

Submission status: Accepted

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

from itertools import combinations, permutations
L = []
for i in range(1,n+1):
    L += list(combinations(N,i))
ans = []
for l in L:
    ans.append(sum(l))
for q in Q:
    if q in ans:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
from collections import defaultdict
dd = defaultdict(lambda:False) # 作れる数はTrue

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

for i in range(1<<len(li_a)):
    sum_ = 0
    # j 桁目が１のときその商品を数字をたす
    for j in range(len(li_a)):
        if (i >> j) & 1:
            sum_ += li_a[j]
    dd[sum_] = True
    
for i in li_m:
    if dd[i]:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
Q = int(input())
M = [int(m) for m in input().split()]

dp = [[None] * 2000 for _ in range(N + 1)]

def solve(i, m):
    if dp[i][m] != None:
        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 M:
    print('yes' if solve(0, 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()))
dp = [[False]*(44000) for i in range(n+1)]
dp[0][0] = True
for i in range(n):
    for j in range(max(a)*n+1):
        dp[i+1][j] |= dp[i][j]
        if j-a[i] >=0:dp[i+1][j] |= dp[i][j-a[i]]
for i in range(q):
    if dp[n][m[i]]:print('yes')
    else:print('no')

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=None)
def search(i, m):
    if m == 0:
        return True
    if i >= n or m < 0:
        return False
    e = (search(i + 1, m) or search(i + 1, m - A[i]))
    return e


for m in M:
    if search(0, m):
        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 = {}
for j in range(2 ** n):
    tot = 0
    for k in range(n):
        tot += ((j >> k) & 1) * A[k]
    flag[tot] = True

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

Submission status: Accepted

Solution code:

def solv():
    n = int(input())
    a = list(map(int,input().split()))
    _ = int(input())
    m = list(map(int,input().split()))
    h = {}
    for v in m:
        h[v] = 0
    c = 0
    while c < (1 << n):
        check = 0
        for i in range(n):
            if c & (1 << i):
                check += a[i]
        if check in h:
            h[check] = 1
        c += 1
    for v in m:
        if h[v]:print("yes")
        else:print("no")

if __name__ == "__main__":
    solv()

Submission status: Accepted

Solution code:
from itertools import product
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    _ = int(readline())
    A = [(0, int(i)) for i in readline().split()]
    _ = int(readline())
    M = [int(i) for i in readline().split()]

    check_list = [0] * (2000+1)
    for a in product(*A):
        sum_a = sum(a)
        if sum_a > 2000:
            continue
        check_list[sum_a] = 1

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


if __name__ == "__main__":
    main()

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()]
lst = [False]*(max(sum(a)+1,max(m)+1))

for i in range(1<<n):
    cnt = 0
    for j in range(n):
        if i >> j & 1: cnt += a[j]
        lst[cnt] = True

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

Submission status: Accepted

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

st = set()
for i in range(2**n):
    sm = 0
    for j in range(n):
        if ((i>>j)&1):
            sm = sm+a[j]
            st.add(sm)
q = int(input())
m = list(map(int,input().split()))
for i in range(q):
    if (m[i] in st):
        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()))

B={0}
C={0}
for num in A:
    for item in B:
        C.add(item+num)
        #print(num,C)
    B |=C
#print(B)

    
for num in m:
  if num in C:
    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 j in range(2**n):
    tmp = 0
    for h in range(n):
        if (j>>h)&1:
            tmp += A[h]
    flag[tmp] = 1

for i in m:
    if flag[i]:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
from bisect import bisect_left
n=int(input())
A=list(map(int,input().split()))
q=int(input())
Q=list(map(int,input().split()))

B=[20*2000+1]
for i in range(2**n):
    num=format(i,"b").zfill(n)
    ans=0
    for j,k in enumerate(num):
        if k=="1":ans +=A[j]
    B.append(ans)

B.sort()
for i in Q:
    if B[bisect_left(B,i)]==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()))
res = ["no"] * Q

for i in range(2 ** N):
    s = 0
    for n in range(N):
        if (i >> n) & 1 == 1:
            s += A[n]
    else:
        if s in M:
            indexes = [j for j, x in enumerate(M) if x == s]
            for index in indexes:
                res[index] = "yes"

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = set()
def cul(x,i):
    global ans
    ans.add(x)
    if n>i:
        cul(x+a[i],i+1)
        cul(x,i+1)
cul(0,0)
q = int(input())
m = list(map(int,input().split()))
for i in m:
    if i in ans: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()))

ans = set()
for i in itertools.product(range(2),repeat=n):
    ans.add(sum(itertools.compress(a,i)))

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

#bit全探索
l = set()
for bit in range(1 << n):
    sum = 0
    for i in range(n):
        if bit & (1 << i):
            sum += A[i]
    l.add(sum)

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

Submission status: Accepted

Solution code:
def dfs(current_sum, index, target, nums):
    if current_sum == target:
        return True
    elif current_sum > target:
        return False
    elif index == len(nums):
        return False
    elif current_sum + sum(nums[index:]) < target:
        return False
    else:
        return dfs(current_sum + nums[index], index + 1, target, nums) or dfs(current_sum, index + 1, target, nums)

n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
m = [int(i) for i in input().split()]
for i in m:
    if dfs(0, 0, i, 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()))

flag = [False for _ in range(q)]
value_dict = {}

for i in range(2 ** n):
    a = 0
    for j in range(n):
        if i >> j & 1:
            a += A[j]
            value_dict[a] = 1
    
for b in M:
    if b in value_dict:
        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()))
A.sort()

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

lst = set(lst)
for i in range(q):
    if(Q[i] in lst):
        print("yes")
    else:
        print("no")

Submission status: Accepted

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


#組み合わせ列挙版



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

  if (i+1,m) in d.keys():
    s1 =  d.get((i+1,m))
  else:
    s1 = solve(i+1, m)
    d[(i+1,m)] = s1
  
  if (i+1, m - A[i]) in d.keys():
    s2 = d.get((i+1, m - A[i]))
  else:
    s2 = solve(i+1, m - A[i])
    d[(i+1,m - A[i])] = s2

  return s1 | s2

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

Submission status: Accepted

Solution code:
import sys

def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


def main():
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    M = list(map(int, input().split()))
    check = []
    for i in range(2 ** n):
        ans = 0
        for j in range(n):
            if (i >> j) & 1:
                ans += A[j]
        check.append(ans)
    for m in M:
        if m in check:
            print("yes")
        else:
            print("no")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())

nums = list(map(int, input().split()))
q = int(input())
target_nums = list(map(int, input().split()))
score_list = []

for i in range(1 << n):
    ans = 0
    for j in range(n):
        if i >> j & 1:
            ans += nums[j]
    score_list.append(ans)
# print(score_list)
for num in target_nums:
    if num in score_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()))
Sums = set()
for i in range(2**n):
    Sum = 0
    for j in range(n):
        if (i >> j) & 1:
            Sum += a[j]
    Sums.add(Sum)

for i in range(q):
    if m[i] in Sums:
        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()))

from functools import lru_cache
@lru_cache(maxsize=2**12)
def solve(i, m):
    if m == 0:
        return True
    if i == n:
        return False
    return solve(i+1, m) or solve(i+1, m-a[i])
for i in m:
    if solve(0, i):
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
import bisect
n=int(input())
A=list(map(int,input().split()))
s=set()
for i in range(2**n):
    sum_=0
    for j in range(n):
        if(i>>j&1):
            sum_+=A[j]
    s.add(sum_)
li=sorted(s)
q=int(input())
M=list(map(int,input().split()))
for m in M:
    b=bisect.bisect_left(li,m)
    if(b<len(li) and li[b]==m):
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
import bisect
n = int(input())
n_list = list(map(int,input().split()))
m = int(input())
m_list = list(map(int,input().split()))
n_list.sort()

long_list = []
for j in range(1<<n):
    ans = 0
    for z in range(n):
        if (j>>z)&1:
            ans += n_list[z]
    long_list.append(ans)

long_list.sort()

#print((long_list))

for j in range(m):
    num = bisect.bisect_left(long_list,m_list[j])
    
    if num <= len(long_list) - 1 and long_list[num] == m_list[j]:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
# a = 1,2,3,4,5,2,1,1
# s = {0}
# for j in a:s |= {x+i for x in s} という手もある
#set()は重複を許さずソート→探索がO(1)

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

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

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

for i in range(q):
    m =  M[i]
    if m in p:
        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()))

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

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)


def solve():

    N = iip()
    A = iip()
    q = iip()
    M = iip()

    l = []
    for i in bitall(N):
        cur = 0
        for f, j in enumerate(i):
            if j == 1:
                cur += A[f]

        l.append(cur)


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





#####################################################ライブラリ集ここから


def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=False):  # 数字のinputをlistで受け取る
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True, num_only=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    if isinstance(l, list):
        l = l[0] # 間違って要素１個のタプルを渡されても受け取る
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  # グラフ作成のための辺をリストで返す
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    for i in s:
        print(i)


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left"): # 関数を二分探索
    l = left
    r = right
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if func(x) == target:
            return x
        elif func(x) > target:
            r = x
        else:
            l = x

    if side == "left" or func(x) == target:
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  # リストを二分探索
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                #for i in path: # 経路圧縮
                #    self.parent[i] = cur
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import  itertools

n=int(input())
q=list(map(int,input().split()))
la=int(input())
m=list(map(int,input().split()))
nums=[0,1]
tmp=[]
for cnt in itertools.product(nums, repeat=n):
    gh = list(cnt)
    ans = 0
    for j in range(len(gh)):
        if gh[j] == 1:
            ans += q[j]
    tmp.append(ans)

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
a = int(input())
comb_num = list(map(int, input().split()))
b = int(input())
ans_num = list(map(int, input().split()))

gen = 1

for i in comb_num:
    gen = gen<<i|gen

for j in ans_num:
    if gen>>j&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()))

l = []
for i in range(1<<N):
    cond = [0]*N
    for j in range(N):
        if 1&(i>>j):  # 右シフトして論理積（bit全探索）
            cond[j] = 1
    s = 0
    for i, j in zip(cond, A):
        if i != 0:
            s += j
    l.append(s)

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

Submission status: Accepted

Solution code:

import sys

readline = sys.stdin.readline

def main():
    n = int(input())
    A = [int(i) for i in readline().split()]
    q = int(input())
    m = list(map(int, readline().split()))

    #print(A)

    sumarray = []
    for i in range(2 ** n):
        select = []
        for j in range(n):
            if (i >> j) & 1:
                select.append(A[j])
        #print(select)
        sumarray.append(sum(select))

    #print(sumarray)
    #print(m)

    for k in [x in sumarray for x in m]:
        #print(k)
        if k:
            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()))
flag = [False]*(2000*n+1)

bit = 2**n-1
for i in range(bit, -1, -1):
    tmp = 0
    tmpbit = i
    for j in range(n):
        if (tmpbit & 1) == 1:
            tmp += A[j]
        tmpbit >>= 1
    flag[tmp] = True

for i in m:
    if flag[i] is True:
        print("yes")
    else:
        print("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()))

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
# import numpy as np
from functools import reduce
import statistics
import decimal
import heapq
import collections
import itertools
from operator import mul

sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===
n = int(input())
tmp = input().split()
items = [int(n) for n in tmp]
m = int(input())
tmp = input().split()
targets = [int(n) for n in tmp]

ans = [0]
for num in items:
    tmp = deepcopy(ans)
    for i in range(len(tmp)):
        tmp[i] += num
    ans.extend(tmp)

a = set(ans)

for tgt in targets:
    if tgt in a:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
n = int(input())
N = list(map(int,input().split()))
m = int(input())
M = list(map(int,input().split()))

sum_lis = []
for i in range(2**n):
    lis = []
    for j in range(n):
        if (i>>j)&1 == 1: #２進数iのj桁目のbitが１ならば
           lis.append(N[j])
#    lis = [N[x] for x in range(n) if (i>>x)&1==1]
    sum_lis.append(sum(lis))
sum_set = set(sum_lis)
#indexでfor文をまわす
for i in range(m):
    if M[i] in  sum_set:
        M[i] = 'yes'
    else:
        M[i] = 'no'
[print(_) for _ in M]

Submission status: Accepted

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

MAX = max(M)
dp = [[0]*(MAX+1) for _ in range(n+1)]
chk = [[0]*(MAX+1) for _ in range(n+1)]


def solve(i, m):
    if not 0 <= m <= MAX:
        return False
    if 1 <= n and chk[i][m]:
        return dp[i][m]

    elif 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

    chk[i][m] = 1
    return dp[i][m]


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

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

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

    a = [False]*(max(m)+1)
    for j in range(2**n):
        s = 0
        for k in range(n):
            if (j >> k) & 1:
                s += A[k]
        if s<=max(m):
            a[s] = True
    for i in m:
        if a[i]:
            print('yes')
        else:
            print('no')

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from itertools import product
N = int(input())
A = tuple(map(int, input().split()))
Q = int(input())
query = tuple(map(int, input().split()))

cand = set()
for p in product(range(2), repeat=N):
    val = sum(x * y for x, y in zip(p, A))
    cand.add(val)

ans = ["yes" if v in cand else "no" for v in query]
print(*ans, sep="\n")