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


def solve(j, i):
    '''A[j]?????§?????¨??????i???M?????????????´??????????A[0],..,A[j]??????????????????????????????
    '''
    if i == 0:
        return True
    if j > n - 1:
        return False

    if i >= A[j]:
        tmp1 = solve(j + 1, i - A[j])
        tmp2 = solve(j + 1, i)
    else:
        # A[j]???????????§???????????§????????????????????????j??????????????\?????????
        return False

    if tmp1 or tmp2:
        return True
    else:
        return False


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

Submission status: Time Limit Exceeded

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

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

	return res

if __name__ == '__main__':
	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(0, M[i]):
			print("yes")
		else:
			print("no")

Submission status: Time Limit Exceeded

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

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

	if m == 0:
		return True
	elif i >= n:
		return False
	
	# ???????????±????????????TLE???????????§????\????????????????????????????????????????????????????
	#res = solve(i + 1, m) + solve(i + 1, m - A[i])
	#return res

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

if __name__ == '__main__':
	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(0, M[i]):
			print("yes")
		else:
			print("no")

Submission status: Time Limit Exceeded

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

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

	if m == 0:
		return True
	elif i >= n:
		return False
	
	# ???????????±????????????TLE???????????§????\????????????????????????????????????????????????????
	#res = solve(i + 1, m) + solve(i + 1, m - A[i])
	#return res

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

if __name__ == '__main__':
	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(0, M[i]):
	#		print("yes")
	#	else:
	#		print("no")

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

Submission status: Time Limit Exceeded

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

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

	if m == 0:
		return True
	elif i >= n:
		return False
	
	# ???????????±????????????TLE???????????§????\????????????????????????????????????????????????????
	#res = solve(i + 1, m) + solve(i + 1, m - A[i])
	#return res

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

if __name__ == '__main__':
	n = int(input())
	#A = list(map(int, input().split()))
	A = [int(i) for i in input().rstrip().split(" ")]
	q = int(input())
	#M = list(map(int, input().split()))
	M = [int(i) for i in input().rstrip().split(" ")]

	#for i in range(q):
	#	if solve(0, M[i]):
	#		print("yes")
	#	else:
	#		print("no")

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

Submission status: Time Limit Exceeded

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

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

	if m == 0:
		return True
	elif i >= n:
		return False
	
	# ???????????±????????????TLE???????????§????\????????????????????????????????????????????????????
	#res = solve(i + 1, m) + solve(i + 1, m - A[i])
	# or??????????????????+????????????
	#return res

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

if __name__ == '__main__':
	n = int(input())
	#A = list(map(int, input().split()))
	A = [int(i) for i in input().rstrip().split(" ")]
	q = int(input())
	#M = list(map(int, input().split()))
	M = [int(i) for i in input().rstrip().split(" ")]

	#for i in range(q):
	#	if solve(0, M[i]):
	#		print("yes")
	#	else:
	#		print("no")

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

Submission status: Time Limit Exceeded

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

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])

if __name__ == '__main__':
	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 -*-

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

n = int(raw_input())
A = map(int, raw_input().split())
q = int(raw_input())
M = map(int, raw_input().split())
for i in range(q):
    if func(0, M[i], A):
        print "yes"
    else:
        print "no"

Submission status: Time Limit Exceeded

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

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

n = int(raw_input())
A = map(int, raw_input().split())
q = int(raw_input())
M = map(int, raw_input().split())
for i in range(q):
    if func(0, M[i]):
        print "yes"
    else:
        print "no"

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf_8 -*-

from itertools import repeat

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)

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()]
    for i in m:
        print("yes") if rec(a, 0, 0, i) > 0 else print("no")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf_8 -*-

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

Submission status: Time Limit Exceeded

Solution code:
def solve(m, A):
    if A[0] == m: return True
    if len(A)==1: return False
    if m < A[0] : return solve(m, A[1:])
    if solve(m-A[0], A[1:]):
        return True
    return solve(m, A[1:])

if __name__=='__main__':
    n=int(input()) 
    A=list(map(int,input().split()))
    q=int(input()) 
    Q=list(map(int,input().split()))
    for m in Q:
        if solve(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 exhaustivesearch(i, target):
    if target == 0:
        return True
    if i >= n:
        return False
    ans = exhaustivesearch(i + 1, target) or exhaustivesearch(i + 1, target-A[i])
    return ans


for j in m:
    if exhaustivesearch(0, j):
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

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

def solve(i, m):
    if m == 0:
        return True
    if i >= n:
        return False
    # i?????????????´?????????°????????£?????´?????¨???????????´?????§?????°????????????
    res = solve(i+1, m) or solve(i+1, m-A[i])
    return res

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

Submission status: Time Limit Exceeded

Solution code:
n1 = int(input())
A = list(map(int, input().split()))
n2 = int(input())
q = list(map(int, input().split()))

B = []

n = n1

for r in q:
    ans = "no"
    for i in range(2 ** n):
        B = list(map(int, format(i, "b").zfill(n)))[::-1]
        C = [ x*y for x, y in zip(A, B)]
        if sum(C) == r:
            ans = "yes"
            break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n1 = int(input())
A = list(map(int, input().split()))
n2 = int(input())
q = list(map(int, input().split()))

B = []

n = n1
ans = list("no" for i in range(n2))

for i in range(2 ** n):
    C0 = []
    B = list(map(int, format(i, "b").zfill(n)))[::-1]
    C0 = [ x*y for x, y in zip(A, B)]
    C = sum(C0)
    for j, r in enumerate(q):
        if  C == r:
            ans[j] = "yes"
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(input())
A = list(map(int, sys.stdin.readline()[:-1].split()))

q = int(input())
M = list(map(int, sys.stdin.readline()[:-1].split()))

def solve(A, n, i, m):
    if i == n:
        return 'no'
    a = A[i]
    if a == m:
        return('yes')
    use = solve(A, n, i+1, m)
    no_use = 'no'
    if a < m:
        no_use = solve(A, n, i+1, m - a)
    if use == 'yes' or no_use == 'yes':
        return 'yes'
    else:
        return 'no'
for m in M:
    print(solve(A, n, 0, m))

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(input())
A = list(map(int, sys.stdin.readline()[:-1].split()))

q = int(input())
M = list(map(int, sys.stdin.readline()[:-1].split()))

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

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

Submission status: Time Limit Exceeded

Solution code:
input()
nlist=map(int, raw_input().split())
input()
qlist=map(int, raw_input().split())

n = len(nlist)

def func(idx, m):
    
    if m==0:
        return True
    
    if idx > n-1:
        return False
    
    res=func(idx+1, m) | func(idx+1, m-nlist[idx])
    
    return res


for q in qlist:
    print "yes" if func(0, q) else "no"

Submission status: Time Limit Exceeded

Solution code:
from sets import Set

input()
n_list=map(int, raw_input().split())
input()
m_list=map(int, raw_input().split())

n = len(n_list)

pool = Set([])

def func(idx, m):

    if m==0:
        return True
    if idx >= n:
        return False
    res = func(idx + 1, m) | func(idx + 1, m - n_list[idx])
    
    if res:
        pool.add(m)
    return res

for v in m_list:
    if v in pool:
        print "yes"
    else:
        print "yes" if func(0, v) else "no"

Submission status: Time Limit Exceeded

Solution code:
#coding:UTF-8
def Solve(n,A,i,m):
    if m==0:
        return True
    if i >= n:
        return False
    res1 = Solve(n,A,i+1,m)
    res2 = Solve(n,A,i+1,m-A[i])
    if res1==True or res2==True:
        return True
    else:
        return False

def ES(n,A,q,m):
    for i in range(q):
        ans=Solve(n,A,0,m[i])
        if ans==True:
            print("yes")
        else:
            print("no")
        
  
if __name__=="__main__":
    n=int(input())
    A=input().split(" ")
    for i in range(n):
        A[i]=int(A[i])
    q=int(input())
    m=input().split(" ")
    for i in range(q):
        m[i]=int(m[i])
    ES(n,A,q,m)

Submission status: Time Limit Exceeded

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=jp

def exhaustive_search(target_list,m):
    t = []
    for i in range(len(target_list)):
        result = m - target_list[i]
        if result == 0:
            return True
        elif result > 0:
            t.append(exhaustive_search(target_list[i+1:], result))

    if True in t:
        return True
    
    return False

if __name__ == "__main__":
    input_data = []
    for i in range(4):
        input_data.append(input())

    target_list = [int(d) for d in input_data[1].split()]
    m_list = [int(d) for d in input_data[3].split()]

    for m in m_list:
        if exhaustive_search(target_list,m):
            print("yes")
        else:
            print("no")

Submission status: Time Limit Exceeded

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=jp

def exhaustive_search(target_list,m):

    for i in range(len(target_list)):
        result = m - target_list[i]
        if result == 0:
            return True
        elif result > 0:
            if exhaustive_search(target_list[i+1:], result):
                return True
                
    return False

if __name__ == "__main__":
    input_data = []
    for i in range(4):
        input_data.append(input())

    target_list = [int(d) for d in input_data[1].split()]
    m_list = [int(d) for d in input_data[3].split()]

    for m in m_list:
        if exhaustive_search(target_list,m):
            print("yes")
        else:
            print("no")

Submission status: Time Limit Exceeded

Solution code:
# encoding: utf-8


import sys

__input = sys.stdin.readlines()
length_1 = int(__input[0])
array_1 = list(map(int, __input[1].split()))
length_2 = int(__input[2])
array_2 = list(map(int, __input[3].split()))


def solution():
    # print(length_1, array_1, length_2, array_2)
    assert length_1 == len(array_1) and length_2 == len(array_2)

    for i in range(length_2):
        ans = solve(0, array_2[i])
        if ans:
            print("yes")
        else:
            print("no")
    return None


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


if __name__ == '__main__':
    solution()

Submission status: Time Limit Exceeded

Solution code:
# encoding: utf-8


import sys

__input = sys.stdin.readlines()
length_1 = int(__input[0])
array_1 = list(map(int, __input[1].split()))
length_2 = int(__input[2])
array_2 = list(map(int, __input[3].split()))
upperbound = 2000
assert length_1 == len(array_1) and length_2 == len(array_2)


def solution_1():
    record = [False] * upperbound

    for i in array_1:
        # record combinations of sums of each in array_1
        for j in range(upperbound - i, 0, -1):
            if record[j]:
                record[int(i + j)] = True
        record[i] = True

    for each in array_2:
        if record[each]:
            print("yes")
        else:
            print("no")


def solution_2():
    for each in array_2:
        # print('e', each)
        ans = solve(0, each)
        if ans:
            print("yes")
        else:
            print("no")


def solve(i, m):
    if m == 0:
        # print('c')
        return True
    if i >= length_1:
        # print('a', i, m)
        return False

    # print('b', i, m)
    ans = solve(i + 1, m) or solve(i + 1, m - array_1[i])
    return ans


if __name__ == '__main__':
    # solution_1()
    solution_2()

Submission status: Time Limit Exceeded

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=jp

def exhaustive_search(target_list,m):

    for i in range(len(target_list)):
        result = m - target_list[i]
        if result == 0:
            return True
        elif result > 0:
            if exhaustive_search(target_list[i+1:], result):
                return True
                
    return False

def main():
    n_input = int(input())
    input_data = [int(a) for a in input().split()]
    n_target = int(input())
    target_list = [int(a) for a in input().split()]

    for m in target_list:
        if exhaustive_search(input_data,m):
            print("yes")
        else:
            print("no")
            
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-

''' '''


def check(n, target, i, sum):
    if i == n:
        return sum == target

    # A[i]???????????´???
    if check(n, target, i + 1, sum + A[i]):
        return True

    # A[i]?????????????????´???
    if check(n, target, i + 1, sum):
        return True

    # A[i]????????£????????????????????????target???????????????
    return False

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

    for b in B:
        if check(n, b, 0, 0):
            print('yes')
        else:
            print('no')

Submission status: Time Limit Exceeded

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

def dfs(sum,target,index):
    if sum==target:
        return True

    if index==n:
        return False

    if target<sum:
        return False

    if dfs(sum+a[index],target,index+1):
        return True

    if dfs(sum,target,index+1):
        return True

    return False

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

Submission status: Time Limit Exceeded

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

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 m in [int(x) for x in input().split()]:
    if solve(0, m):
        print('yes')
    else:
        print('no')

Submission status: Time Limit Exceeded

Solution code:
def solve(p, t):
  if p >= len(A): return False
  if t == A[p]: return True
  if t <= 0: return False
  #print("({}, {})".format(p, t))

  if solve(p + 1, t):
    return True
  else:
    return solve(p + 1, t - A[p])

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

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

Submission status: Time Limit Exceeded

Solution code:
class Solver():
    def __init__(self, A: [int]):
        self.A = A
        self.max_depth = len(A)

    def solve(self, tgt):
        self.tgt = tgt
        if self._rec_solve(0, 0):
            return 'yes'
        else:
            return 'no'

    def _rec_solve(self, _sum, index):
        if _sum == self.tgt:
            return True
        elif index >= self.max_depth or _sum > self.tgt:
            return False
        else:
            return self._rec_solve(_sum + self.A[index], index + 1) or self._rec_solve(_sum, index + 1)
            


if __name__ == '__main__':
    n = int(input())
    A = [int(i) for i in input().rstrip().split()]
    q = int(input())
    m_ary = [int(i) for i in input().rstrip().split()]
    s = Solver(A)
    for i in m_ary[:]:
        print(s.solve(i))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stderr

def rec(A, i, m):
    if i == 0:
        return m == 0 or A[i] == m

    return rec(A, i - 1, m) or rec(A, i - 1, m - A[i])

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

for m in M:
    if rec(A, n - 1, m):
        print('yes')
    else:
        print('no')

Submission status: Time Limit Exceeded

Solution code:
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

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

#makeCombination()
for j in range(q):
    if solve(0,m[j]) == True:
        print('yes')
    else:
        print('no')

Submission status: Time Limit Exceeded

Solution code:
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

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

for j in range(q):
    if solve(0,m[j]):
        print('yes')
    else:
        print('no')

Submission status: Time Limit Exceeded

Solution code:
n = input()
A = input().split(' ')
A.sort()
q = input()
M = input().split(' ')

A = list(map(int,A))
M = list(map(int,M))

memo = [True]*(len(A))

def search(base, m):
    if base == m:
        return True
    result = False
    for i in range(len(A)):
        if base + A[i] <= m and memo[i]:
            memo[i] = False
#           print(str(A[i]) + ',' + str(base+A[i]) + ',')
            result = result or search(base+A[i], m)
            memo[i] = True
    return result

def print_yn(result):
    if result:
        print('yes')
    else:
        print('no')

for m in M:
#   print(str(m)+':')
    print_yn(search(0,m))

Submission status: Time Limit Exceeded

Solution code:
n = input()
A = input().split(' ')
A.sort()
q = input()
M = input().split(' ')

A = list(map(int,A))
M = list(map(int,M))

#memo = [True]*(len(A))

def search(base, m, n):
    if base == m:
        return True
    result = False
    for i in range(n,len(A)):
        if base + A[i] <= m: # and memo[i]:
#           memo[i] = False
#           print(str(A[i]) + ',' + str(base+A[i]) + ',')
            result = result or search(base+A[i], m, i+1)
#           memo[i] = True
    return result

def print_yn(result):
    if result:
        print('yes')
    else:
        print('no')

for m in M:
#   print(str(m)+':')
    print_yn(search(0,m,0))

Submission status: Time Limit Exceeded

Solution code:
n = input()
A = input().split(' ')
A.sort()
q = input()
M = input().split(' ')

A = list(map(int,A))
M = list(map(int,M))

#memo = [True]*(len(A))

def search(base, m, n):
    if base == m:
        return True
    result = False
    for i in range(n,len(A)):
        if base + A[i] <= m: # and memo[i]:
#           memo[i] = False
#           print(str(A[i]) + ',' + str(base+A[i]) + ',')
            if search(base+A[i], m, i+1):
                return True
#           memo[i] = True
    return result

def print_yn(result):
    if result:
        print('yes')
    else:
        print('no')

for m in M:
#   print(str(m)+':')
    print_yn(search(0,m,0))

Submission status: Time Limit Exceeded

Solution code:
n = input()
A = input().split(' ')
A.sort()
A.reverse()
q = input()
M = input().split(' ')

A = list(map(int,A))
M = list(map(int,M))

#memo = [True]*(len(A))

def search(base, m, n):
    if base == m:
        return True
    result = False
    for i in range(n,len(A)):
        if base + A[i] <= m: # and memo[i]:
#           memo[i] = False
#           print(str(A[i]) + ',' + str(base+A[i]) + ',')
            if search(base+A[i], m, i+1):
                return True
#           memo[i] = True
    return result

def print_yn(result):
    if result:
        print('yes')
    else:
        print('no')

for m in M:
#   print(str(m)+':')
    print_yn(search(0,m,0))

Submission status: Time Limit Exceeded

Solution code:
n = input()
A = input().split(' ')
A.sort()
A.reverse()
q = input()
M = input().split(' ')

A = list(map(int,A))
M = list(map(int,M))
A.sort()

A_sum = [0]
for a in A:
    A_sum.append(a+A_sum[-1])

A.reverse()


#memo = [True]*(len(A))

def search(base, m, n):
    if base == m:
        return True
    result = False
    for i in range(n,len(A)):
        if base + A[i] <= m: # and memo[i]:
#           memo[i] = False
#           print(str(A[i]) + ',' + str(base+A[i]) + ',')
            if search(base+A[i], m, i+1):
                return True
#           memo[i] = True
    return result

def print_yn(result):
    if result:
        print('yes')
    else:
        print('no')

for m in M:
#   print(str(m)+':')
    print_yn(search(0,m,0))

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools

def can_be_composed(n, m, A):
	for i in range(1, n + 1):
		combination_list = list(itertools.combinations(A, i))
		for l in combination_list:
			if m == sum(l):
				return True

	return False

#fin = open("test.txt", "r")
fin = sys.stdin

n = int(fin.readline())
A = list(map(int, fin.readline().split()))
q = int(fin.readline())
m_list = list(map(int, fin.readline().split()))
for m in m_list:
	if can_be_composed(n, 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):
    a = 0
    if a ==m:
        return True
    if i >= n:
        return False
    
    res = solve(i+1,m) or solve(i+1,m-A[i])
    return res 

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def solve(pos, tot, A):
    if tot == 0: return True
    if pos > len(A) - 1: return False

    return solve(pos+1, tot - A[pos], A) or \
           solve(pos+1, tot, A)

n = raw_input()
b = map(int, raw_input().split())
n = raw_input()
t = map(int, raw_input().split())

for tt in t:
    print 'yes' if True == solve(0, tt, b) else 'no'

Submission status: Time Limit Exceeded

Solution code:
import itertools
given_n = int(input())
given_A = list(map(int,input().split()))
given_q = int(input())
given_m = list(map(int,input().split()))

for mi in given_m:
    partial_A = list(filter(lambda ai:ai<=mi,given_A))
    check = False
    for num in range(1,len(partial_A)+1):
        combinationPartialA = list(itertools.combinations(partial_A,num))
        for tmp_cpa in combinationPartialA:
            if sum(tmp_cpa) == mi:
                check = True
    if check:
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

Solution code:
import itertools
given_n = int(input())
given_A = list(map(int,input().split()))
given_q = int(input())
given_m = list(map(int,input().split()))

for mi in given_m:
    partial_A = list(filter(lambda ai:ai<=mi,given_A))
    check = False
    for num in range(1,len(partial_A)+1):
        combinationPartialA = list(itertools.combinations(partial_A,num))
        for tmp_cpa in combinationPartialA:
            if sum(tmp_cpa) == mi:
                check = True
                break
        if check:
            break
    if check:
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

Solution code:
def solve(m, A, i):
	if m==0: return True
	if i>n-1: return False

	f1 = solve(m-A[i], A, i+1)
	f2 = solve(m, A, i+1)

	return f1 or f2


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

for m in map( int, input().split() ):
	print( 'yes' if solve(m, A, 0) else 'no')

Submission status: Time Limit Exceeded

Solution code:
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

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

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

Submission status: Time Limit Exceeded

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

import sys
import os


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

# query
q = int(input())
M = list(map(int, input().split()))

def solve(i, m):
    #print('i', i, 'm', m)

    # i????????\???????????????????????£???m??????????????¨???true
    # i = 0, ..., n-1
    if m == 0:
        return True
    elif i >= n:
        return False
    else:
        # Devide and Conquer

        # i??????????????°??????
        res0 = solve(i + 1, m)
        # i??????????????¶
        res1 = solve(i + 1, m - A[i])

        if res0 or res1:
            return True
        else:
            return False


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

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8


def solve_recursively(candidate_numbers, target_number):
    """classify if the target number is represented a summation of elements of candidate_numbers

    Args:
        candidate_numbers: candidate_numbers
        target_number: target_number

    Returns:
        if target number is represented a summation of elements of candidate_numbers(book)
    """
    if target_number == 0:
        return True
    elif len(candidate_numbers) == 0:
        return False

    solution = solve_recursively(candidate_numbers[1:], target_number - candidate_numbers[0]) or solve_recursively(
        candidate_numbers[1:], target_number)

    return solution


def main():
    raw_input()  # pass length
    candidate_numbers = [int(x) for x in raw_input().strip().split(' ')]
    raw_input()  # pass length
    target_numbers = [int(x) for x in raw_input().strip().split(' ')]

    for target_number in target_numbers:
        if solve_recursively(candidate_numbers, target_number):
            print "yes"
        else:
            print "no"


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

def f(A, s, res):
  if res[0]:
    return
  if s == 0:
    res[0] = True
    return
  for i, a in enumerate(A):
    if a > s:
      break
    f(A[i+1:], s-a, res)

for mi in m:
  res = [False]
  f(A, mi, res)
  if res[0]:
    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 = list(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 m in Mi:
 for i in range(n):
  if solve(i, m):
   print("yes")
   break
  if i == n-1 and not(solve(i,m)):
   print("no")