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: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

def canProd(a,x):
    for i in range(1,len(a)+1):
        comba = combinations(a,i)
        for j in comba:
            if sum(j) == x:
                return True
    return False


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

for i in m:
    if canProd(a,i):
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

cpList = []

def canProd(a,x):
    if x in cpList:
        return True
    for i in range(1,len(a)+1):
        comba = combinations(a,i)
        for j in comba:
            if sum(j) == x:
                cpList.append(x)
                return True
    return False


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

for i in m:
    if canProd(a,i):
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

cpList = []

def canProd(a,x):
    if x in cpList:
        return True

    b = [t for t in a if t <= x]

    for i in range(1,len(b)+1):
        comba = combinations(b,i)
        for j in comba:
            if sum(j) == x:
                cpList.append(x)
                return True
    return False


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

for i in m:
    if canProd(a,i):
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

Solution code:

def canProd(i,m,a,n):
    
    if m == 0:
        return True
    if i >= n:
        return False

    res = canProd(i+1,m,a,n) or canProd(i+1,m-a[i],a,n)
    return res


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

for i in m:
    if canProd(0,i,a,n):
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

Solution code:

def canProd(i,m,a,n):
    
    if m == 0:
        return True
    if i >= n:
        return False

    res = canProd(i+1,m,a,n) or canProd(i+1,m-a[i],a,n)
    return res


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

tf = []

for i in range(1,2001):
    if canProd(0,i,a,n):
        tf.append(i)



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

Submission status: Time Limit Exceeded

Solution code:

def canProd(i,m,a,n):
    
    if m == 0:
        return True
    if i >= n:
        return False

    res = canProd(i+1,m,a,n) or canProd(i+1,m-a[i],a,n)
    return res


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

tf = []

for i in range(min(m),max(m)+1):
    if canProd(0,i,a,n):
        tf.append(i)



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

Submission status: Time Limit Exceeded

Solution code:

def canProd(i,m,a,n):
    
    if m == 0:
        return True
    if i >= n:
        return False

    res = canProd(i+1,m,a,n) or canProd(i+1,m-a[i],a,n)
    return res


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

tf = [False]*2001

for i in range(min(m),max(m)+1):
    if canProd(0,i,a,n):
        tf[i] = True



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

Submission status: Time Limit Exceeded

Solution code:

def canProd(i,m):
    
    if m == 0:
        return True
    if i >= n:
        return False

    res = canProd(i+1,m) or canProd(i+1,m-a[i])
    return res


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

tf = [False]*2001

for i in range(min(m),max(m)+1):
    if canProd(0,i):
        tf[i] = True



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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def solve(i, m, n, a_numbers):
    # ???????????????????????????????????????????????§????????????????????????
    if m == 0: return 1
    if i >= n: return 0

    return solve(i + 1, m, n, a_numbers) or solve(i + 1, m - a_numbers[i], n, a_numbers)


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

for j in range(n2):
    if solve(0, t[j], n, a):
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

Solution code:
def check(A, n,  mi):
    i, E, s = 0, [0 for i in range(n)], 0
    while i < n:
        if s == mi: return True
        if E[i] == 0:
            s += A[i]
            E[i] = 1
            i = 0
        else:
            E[i] = 0
            s -= A[i]
            i += 1
    return False

def ALDS1_5A():
    n, A, q = int(input()),list(map(int, input().split())), int(input())
    for m in input().split():
        if check(A, n, int(m)):
            print('yes')
        else:
            print('no')

if __name__ == '__main__':
    ALDS1_5A()

Submission status: Time Limit Exceeded

Solution code:
def solve(i, m, n, a_numbers):
    # ???????????????????????????????????????????????§????????????????????????
    if m == 0: return 1
    if i >= n: return 0

    return solve(i + 1, m, n, a_numbers) or solve(i + 1, m - a_numbers[i], n, a_numbers)


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


for j in range(n2):
    if solve(0, t[j], n, a):
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

Solution code:

class ExhaustiveSearch:
	def solve(self, A, M):
		for m in M:
			if self.search(0, m):
				print("yes")
			else:
				print("no")

	def search(self, i, m):
		if m == 0:
			return True
		elif i >= n:
			return False

		return self.search(i + 1, m) or self.search(i + 1, m - A[i])


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

x = ExhaustiveSearch()
x.solve(A, M)

Submission status: Time Limit Exceeded

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


def exhaustive(n, target, lst):
    if n == target:
        return True
    if n > target or lst == []:
        return False
    else:
        for i, val in enumerate(lst, 1):
            if exhaustive(n + val, target, lst[i:]):
                return True
    return False


def main(data, targets):
    for target in targets:
        if exhaustive(0, target, data):
            print("yes")
        else:
            print("no")


if __name__ == "__main__":
    lst = [val.split() for val in sys.stdin.read().splitlines()]
    data = [int(n) for n in lst[1]]
    targets = [int(n) for n in lst[3]]
    main(data, targets)

Submission status: Time Limit Exceeded

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

    res = solve(i + 1, m) or solve(i + 1, m - A[i])
    return res

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

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

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

Submission status: Time Limit Exceeded

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

    res = solve(i + 1, m) or solve(i + 1, m - A[i])
    return res


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

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

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

Submission status: Time Limit Exceeded

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

    r1 = solve(i + 1, m)
    r2 = solve(i + 1, m - A[i])

    return r1 or r2


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

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

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

Submission status: Time Limit Exceeded

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

def ALDS1_5A():
    n, A, q = int(input()), list(map(int, input().split())), int(input())
    for Mj in input().split():
        if CanItBeCreated(A, n, 0, int(Mj)):
            print('yes')
        else:
            print('no')
if __name__ == '__main__':
    ALDS1_5A()

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

for j in mi:
    if solve(0, j):
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

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
    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: Time Limit Exceeded

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


def solve(i, m, A): 
    if m == 0:
        return True
    elif i >= n:
        return False
    res = solve(i + 1, m, A) or solve(i + 1, m - A[i], A)
    return res
 
for m in M:
    if solve(0, m, A):
        print('yes')
    else:
        print('no')

Submission status: Time Limit Exceeded

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
    elif i >= n:
        return False
    else:
        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: Time Limit Exceeded

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

table = [[]*n]*max(M)

def solve(i, m): 
    if m == 0:
        return True
    elif i >= n:
        return False
    else:
        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: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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
    elif i >= n:
        return False
    elif m - A[i] >= 0:
        res = solve(i + 1, m) or solve(i + 1, m - A[i])
        return res
    else:
        res = solve(i + 1, m)
        return res

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

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def solve(Mi,i):
	if Mi == 0: return True
	if i < n and Mi > 0:
		r1 = solve(Mi-A[i],i+1)
		r2 = solve(Mi,i+1)
		if r1: return r1
		if r2: return r2
n = input()
A = map(int,raw_input().split())
q = input()
M = map(int,raw_input().split())
for Mi in M:
	print "yes" if solve(Mi,0) else "no"

Submission status: Memory Limit Exceeded

Solution code:
import itertools as it

def check(p, li):
    li_ad = [i for i in li if i <= p]
    flag = False
    for j in range(len(li_ad)):
        li_perm = list(it.permutations(li_ad, j+1))
        for k in range(len(li_perm)):
            if sum(li_perm[k]) == p:
                flag = True
                break
        if flag:
            break
        
    return flag
    
    
n = int(input())
A = sorted(list(map(int, input().split())))
q = int(input())
m = list(map(int, input().split()))

min_range = A[0]
max_range = sum(A)

for i in range(q):
    if m[i] < min_range or m[i] > max_range:
        print('no')
    else:
        print('yes' if check(m[i], A) else 'no' )

Submission status: Memory Limit Exceeded

Solution code:
import itertools as it
    
n = int(input())
A = sorted(list(map(int, input().split())))
q = int(input())
m = list(map(int, input().split()))

s = set()

for i in range(n):
    li= list(it.permutations(A, i+1))
    for j in range(len(li)):
        s.add(sum(li[j]))

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import repeat
from itertools import combinations

def rec(s, i, total, m):
    if total == m:
        return 1

    if len(s) == i or total > m:
        return 0

    return rec(s, i + 1, total, m) + rec(s, i + 1, total + s[i], m)


def makeCache(s):
    cache = {}
    for i in range(len(s)):
        comb = list(combinations(s, i))
        for c in comb:
            cache[sum(c)] = 1

    return cache

def loop(s, m):
    for i in range(len(s)):
        comb = list(combinations(s, i))
        for c in comb:
            if sum(c) == m:
                return 1

    return 0

if __name__ == "__main__":
    n = int(input())
    a = [int (x) for x in input().split()]
    q = int(input())
    m = [int (x) for x in input().split()]
    s = makeCache(a)
    for i in m:
        #print("yes") if rec(a, 0, 0, i) > 0 else print("no")
        #print("yes") if loop(a, i) > 0 else print("no")
        print("yes") if i in s else print("no")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
# count on j
# 最初に入力したリスト

q = int(input())
m = list(map(int, input().split()))
# count on i
# 後に入力したリスト


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


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

Submission status: Accepted

Solution code:

def solve(a, m):
	dict = {}
	return solve_(a, 0, m, dict)

def solve_(a, i, m, dict):
	res = False
	key = str(i) + '-' + str(m)
	if key in dict:
		res = dict[key]
	elif m == 0:
		res = True
	elif i >= len(a):
		res = False
	else:
		res1 = solve_(a, i + 1, m, dict)
		res2 = solve_(a, i + 1, m - a[i], dict)
		res = res1 or res2
	dict[key] = res
	return res

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

exhaustive_dict = {}

def create_exhastive_list(head, sum):
    for i in range(head, N):
        sum += A[i]
        exhaustive_dict[sum] = 1
        create_exhastive_list(i+1, sum)
        sum -= A[i]

head = 0
sum = 0
create_exhastive_list(head, sum)

for target in M:
    if target in exhaustive_dict.keys():
        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()))

combinations = {}

def create_combinations(idx, sum):
    combinations[sum] = 1
    if idx >= N:
        return
    create_combinations(idx+1, sum)
    create_combinations(idx+1, sum+A[idx])
    return

create_combinations(0, 0)

for target in M:
    if target in combinations.keys():
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
n = int(input())
seq = list(map(int, input().split()))
q = int(input())
mlist = list(map(int, input().split()))
mins = min(seq)
sums = 0
for a in seq:
    sums += a

def check(i, m):
    global mins
    if m == 0:
        return True
    elif i >= n or mins > m:
        return False
    res = check(i+1, m) or check(i+1, m - seq[i])
    return res

for m in mlist:
    if (mins > m or sums < m):
        print('no')
    elif(check(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()))
bits = 1
for a in A:
    bits |= bits << a
for m in M:
    print('yes' if (bits >> m) & 1 else 'no')

Submission status: Accepted

Solution code:
def subset_sum(s, a):
	dict = {}
	return subset_rec(0, s, a, dict)
	
def subset_rec(i, s, a, dict):
	key = str(i) + '-' + str(s)
	ret = False
	if key in dict:
		ret = dict[key]
	elif s == 0:
		ret = True
	elif i >= len(a):
		ret =  False
	else:
		ret = subset_rec(i+1, s-a[i], a, dict) or subset_rec(i+1, s, a, dict)
	dict[key] = ret
	return ret	

n = int(input())
a = list(map(int, input().split()))
p = int(input())
q = list(map(int, input().split()))
for i in range(p):
	if subset_sum(q[i], a):
		print('yes')
	else:
		print('no')

Submission status: Accepted

Solution code:
def subset_sum(s, a):
	dict = {}
	return subset_rec(0, s, a, dict)
	
def subset_rec(i, s, a, dict):
	key = str(i) + '-' + str(s)
	if key in dict:
		ret = dict[key]
	elif s == 0:
		ret = True
	elif i >= len(a):
		ret =  False
	else:
		ret = subset_rec(i+1, s-a[i], a, dict) or subset_rec(i+1, s, a, dict)
	dict[key] = ret
	return ret

n = int(input())
a = list(map(int, input().split()))
p = int(input())
q = list(map(int, input().split()))
for i in range(p):
	if subset_sum(q[i], a):
		print('yes')
	else:
		print('no')

Submission status: Accepted

Solution code:
def subset_sum(s, a):
	n = len(a)
	dp = [[False for x in range(s+1)] for x in range(n+1)]
	for i in range(n):
		v = a[i]
		for j in range(s+1):
			if v == j:
				dp[i+1][j] = True
			elif v > j:
				dp[i+1][j] = dp[i][j]
			else:
				dp[i+1][j] = dp[i][j] or dp[i][j-v]
	return dp[n][s]

n = int(input())
a = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
for i in range(q):
	if subset_sum(m[i], a) == True:
		print('yes')
	else:
		print('no')

Submission status: Accepted

Solution code:
def subset_sum(s, a):
	n = len(a)
	dp = [[False for x in range(s+1)] for x in range(n+1)]
	for i in range(n):
		v = a[i]
		for j in range(s+1):
			if v == j:
				dp[i+1][j] = True
			elif v > j:
				dp[i+1][j] = dp[i][j]
			else:
				dp[i+1][j] = dp[i][j] or dp[i][j-v]
	return dp[n][s]

n = int(input())
a = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
for i in range(q):
	if subset_sum(m[i], a) == True:
		print('yes')
	else:
		print('no')

Submission status: Accepted

Solution code:
def subset_sum(n, s, a):
	dp = [[0 for x in range(s+1)] for x in range(n+1)]
	for i in range(n):
		v = a[i]
		for j in range(s+1):
			if v==j or (v<j and dp[i][j-v]>0):
				dp[i+1][j] = dp[i][j] + 1
			else:
				dp[i+1][j] = dp[i][j]
	return dp[n][s] > 0

n = int(input())
a = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
for i in range(q):
	if subset_sum(n, m[i], a) == True:
		print('yes')
	else:
		print('no')

Submission status: Accepted

Solution code:
# -*- coding=utf-8 -*-
import itertools

count = int(input())
_list = list(map(int, input().split(" ")))

count2 = int(input())
_answers = list(map(int, input().split(" ")))

desc = []
checked = False

# answersの数だけloopして取ってくる
for answer in _answers:
    checked = False
    tmp = [i for i in _list if answer >= i]

    # そもそもtmpの中身をsumしてanswer未満ならば強制的にno
    if answer > sum(tmp):
        desc.append("no")

    # itertoolsのコンビネーションを使用して解く
    else:
        for i in range(len(tmp) + 1):
            if checked == True:
                break

            tmp2 = list(itertools.combinations(tmp, i))
            for tmp3 in tmp2:
                if sum(tmp3) == answer:
                    desc.append("yes")
                    checked = True
                    break

        if checked != True:
            desc.append("no")

for i in desc:
    print(i)

Submission status: Accepted

Solution code:
def main():
    input()
    array_a = list(map(int, input().split()))
    input()
    array_q = map(int, input().split())

    def can_construct_q (q, i, sum_sofar):
        if sum_sofar == q or sum_sofar + array_a[i] == q:
            return True
        elif sum_sofar > q or i >= len (array_a) - 1:
            return False
        if can_construct_q(q, i + 1, sum_sofar + array_a[i]):
            return True
        if can_construct_q(q, i + 1, sum_sofar):
            return True
    sum_array_a = sum(array_a)
    for q in array_q:
        #print(q)
        if sum_array_a < q:
            print('no')
        elif can_construct_q(q, 0, 0):
            print('yes')
        else:
            print('no')
    return


main()

Submission status: Accepted

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

"""
全探索
・再帰で作る
・2^20でTLEするからメモ化した
"""

N = int(input())
aN = list(map(int, input().split()))
Q = int(input())
mQ = list(map(int, input().split()))

def dfs(cur, depth, ans):
    # 終了条件
    if cur == ans:
        return True
    # memo[現在位置]に数値curがあれば、そこから先はやっても同じだからやらない
    if cur in memo[depth]:
        return False
    memo[depth].add(cur)
    # 全探索
    for i in range(depth, N):
        if dfs(cur+aN[i], i+1, ans):
            return True
    # 見つからなかった
    return False

for i in range(Q):
    memo = [set() for j in range(N+1)]
    if dfs(0, 0, mQ[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()))

def test(i, s, target):
    if s == target:
        return 1
    if s > target or i == n:
        return 0
    if s + sum(a[i:]) < target:
        return 0

    return test(i+1, s, target) or test(i+1, s+a[i], target)

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

Submission status: Accepted

Solution code:
a={0}
input()
for c in raw_input().split():
    for i in a.copy(): a.add(i+int(c))
input()
for c in raw_input().split():
    print "yes" if int(c) in a else "no"

Submission status: Accepted

Solution code:
import itertools

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

Submission status: Accepted

Solution code:
n=int(raw_input())
a=map(int,raw_input().split())
q=int(raw_input())
m=map(int,raw_input().split())
ans=set()
p=(1<<n)-1
while p:
    w=str(bin(p))[2:]
    bits='0'*(n-len(w))+w
    p-=1
    k=0
    for i,j in enumerate(bits):
        if j=='1':
            k+=a[i]
    ans.add(k)
for i in m:
    print 'yes' if i in ans else 'no'

Submission status: Accepted

Solution code:
isExist = [0]*2001 
n = int( input() )
A = [ int( val ) for val in input().rstrip().split( ' ' ) ]
for i in A:
	for j in range( 2000-i, 0, -1 ):
		if 1 == isExist[j]:
			isExist[ i+j ] = 1
	isExist[i] = 1

q = int( input() )
M = [ int( val ) for val in input().rstrip().split( ' ' ) ]
for i in range( 0, q ):
	if 1 == isExist[ M[i] ]:
		print( "yes" )
	else:
		print( "no" )

Submission status: Accepted

Solution code:
isExist = [False]*2001 
n = int( input() )
A = [ int( val ) for val in input().rstrip().split( ' ' ) ]
for i in A:
	for j in range( 2000-i, 0, -1 ):
		if isExist[j]:
			isExist[ i+j ] = True
	isExist[i] = True

q = int( input() )
M = [ int( val ) for val in input().rstrip().split( ' ' ) ]
for i in range( 0, q ):
	if isExist[ M[i] ]:
		print( "yes" )
	else:
		print( "no" )

Submission status: Accepted

Solution code:
isExist = [False]*2001 
n = int( raw_input() )
A = [ int( val ) for val in raw_input().rstrip().split( ' ' ) ]
for i in A:
	for j in range( 2000-i, 0, -1 ):
		if isExist[j]:
			isExist[ i+j ] = True
	isExist[i] = True

q = int( raw_input() )
M = [ int( val ) for val in raw_input().rstrip().split( ' ' ) ]
for i in range( 0, q ):
	if isExist[ M[i] ]:
		print( "yes" )
	else:
		print( "no" )

Submission status: Accepted

Solution code:
def solve( p, t ):
	global isExist
	global n
	global A
	isExist[ t ] = True
	if p < n:
		solve( p+1, t-A[p] )
		solve( p+1, t )
	else:
		return

isExist = [False]*2001 
n = int( raw_input() )
A = [ int( val ) for val in raw_input().rstrip().split( ' ' ) ]
q = int( raw_input() )
M = [ int( val ) for val in raw_input().rstrip().split( ' ' ) ]
s = sum( A )
solve( 0, s )
for i in range( 0, q ):
	if isExist[ M[i] ]:
		print( "yes" )
	else:
		print( "no" )

Submission status: Accepted

Solution code:
def solve( p, t ):
	global isExist, n, A
	isExist[ t ] = True
	if p < n:
		solve( p+1, t-A[p] )
		solve( p+1, t )
	else:
		return

isExist = [False]*2001 
n = int( raw_input() )
A = map( int, raw_input().rstrip().split( " " ) )
q = int( raw_input() )
M = map( int, raw_input().rstrip().split( " " ) )
s = sum( A )
solve( 0, s )
for i in range( 0, q ):
	if isExist[ M[i] ]:
		print( "yes" )
	else:
		print( "no" )

Submission status: Accepted

Solution code:
def solve( p, t ):
	global isExist, n, A
	isExist[ t ] = True
	if p < n:
		solve( p+1, t-A[p] )
		solve( p+1, t )
	else:
		return

isExist = [False]*2001 
n = int( input() )
A = [ int( val ) for val in input().rstrip().split( ' ' ) ]
q = int( input() )
M = [ int( val ) for val in input().rstrip().split( ' ' ) ]
s = sum( A )
solve( 0, s )
for i in range( 0, q ):
	if isExist[ M[i] ]:
		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 = map(int, input().split())

s = set()
for i in range(1, n):
    for j in combinations(a, i):
        s.add(sum(j))
for ans in m:
    print('yes' if ans in s else 'no')

Submission status: Accepted

Solution code:
from itertools import combinations

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

s = set()
for i in range(1, n + 1):
    for j in combinations(a, i):
        s.add(sum(j))
for ans in m:
    print('yes' if ans in s else 'no')

Submission status: Accepted

Solution code:
n = int(raw_input())
A = map(int, raw_input().split())
d = {}

def soleve(i, m, n):
    if m == 0:
        return True
    if i >= n:
        return False
    if d.has_key((i, m)):
        return d[(i, m)]
    res = soleve(i + 1, m, n) or soleve(i + 1, m - A[i], n)
    d[(i, m)] = res
    return res


q = int(raw_input())
M = map(int, raw_input().split())
for m in M:
    if soleve(0, m, n):
        print 'yes'
    else:
        print 'no'