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())
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:
 if solve(0, m):
  print("yes")
 else:
  print("no")

Submission status: Time Limit Exceeded

Solution code:

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

def solve(I, M):
    
    if M == 0:
        return True
    if I >= n:
        return False
    if q[I] == M:
        return True
    res = solve(I+1, M) or solve(I+1, M-q[I])
    return res


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

Submission status: Time Limit Exceeded

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

    for m in M:
        for j in range(n):
            w = rec(m,A[j:])

            if w:
                break
        if w:
            print "yes"
        else:
            print "no"

def rec(m,A):
    m_new = m
    if m_new == 0:
        r1 = True
    elif m_new < 0:
        r1 = False
    else:
        if len(A) == 1:
            r1 = False
        else:
            r1 = rec(m_new,A[1:])

    m_new = m - A[0]
    if m_new == 0:
        r2 = True
    elif m_new < 0:
        r2 = False
    else:
        if len(A) == 1:
            r2 = False
        else:
            r2 = rec(m_new,A[1:])

    if r1 or r2:
        return True
    else:
        return False

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    for m in M:
        for j in range(n):
            w = rec(m,A[j:])
            if w:
                break
        if w:
            print "yes"
        else:
            print "no"

def rec(m,A):
    r1 = rec1(m,A)
    r2 = rec1(m-A[0],A)

    if r1 or r2:
        return True
    else:
        return False

def rec1(m_new,A):
    if m_new == 0:
        return True
    elif m_new < 0:
        return False
    else:
        if len(A) == 1:
            return False
        else:
            return rec(m_new,A[1:])
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


def main():
	n = int(input())
	A = input()
	A = A.split()
	q = int(input())
	ms= input()
	for m in ms.split():
		if solve(A, int(m)):
			print('yes')
		else:
			print('no')

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    n = input()
    A = map(int,raw_input().split())
    q = input()
    M = map(int,raw_input().split())

    for m in M:
        qA = deque(A)
        for j in range(n):
            w = rec(m,A)
            if w:
                break
            qA.popleft()
            
        if w:
            print "yes"
        else:
            print "no"

def rec(m,A):
    Ac = deque(list(A)[:])
    Ad = deque(list(A)[:])
    r1 = rec1(m,Ac)
    r2 = rec1(m-A[0],Ad)

    if r1 or r2:
        return True
    else:
        return False

def rec1(m_new,A):
    #print A
    if m_new == 0:
        return True
    elif m_new < 0:
        return False
    else:
        if len(A) == 1:
            return False
        else:
            A.popleft()
            return rec(m_new,A)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
	n = int(input())
	A = input()
	A = A.split()
	q = int(input())
	ms= input()
	for m in ms.split():
		if solve(A, int(m)):
			print('yes')
		else:
			print('no')

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    n = input()
    A = map(int,raw_input().split())
    q = input()
    M = map(int,raw_input().split())

    for m in M:
        w = sub(m,n,A)
        print w
        
def sub(m,n,A):
    qA = deque(A)
    for j in range(n):
        w = rec(m,qA)
        if w:
            break
        qA.popleft()            
    if w:
        return "yes"
    else:
        return "no"
    
def rec(m,A):
    Ac = deque(list(A)[:])
    Ad = deque(list(A)[:])
    r1 = rec1(m,Ac)
    r2 = rec1(m-A[0],Ad)

    if r1 or r2:
        return True
    else:
        return False

def rec1(m_new,A):
    #print A
    if m_new == 0:
        return True
    elif m_new < 0:
        return False
    else:
        if len(A) == 1:
            return False
        else:
            A.popleft()
            return rec(m_new,A)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    n = input()
    A = map(int,raw_input().split())
    q = input()
    M = map(int,raw_input().split())

    W = map(lambda m:sub(m,n,A), M)
    for w in W:
        print w
        
def sub(m,n,A):
    qA = deque(A)
    for j in range(n):
        w = rec(m,qA)
        if w:
            break
        qA.popleft()            
    if w:
        return "yes"
    else:
        return "no"
    
def rec(m,A):
    Ac = deque(list(A)[:])
    Ad = deque(list(A)[:])
    r1 = rec1(m,Ac)
    r2 = rec1(m-A[0],Ad)

    if r1 or r2:
        return True
    else:
        return False

def rec1(m_new,A):
    #print A
    if m_new == 0:
        return True
    elif m_new < 0:
        return False
    else:
        if len(A) == 1:
            return False
        else:
            A.popleft()
            return rec(m_new,A)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    n = input()
    A = map(int,raw_input().split())
    q = input()
    M = map(int,raw_input().split())

    W = map(lambda m:sub(m,n,A), M)
    for w in W:
        print w
        
def sub(m,n,A):
    qA = deque(A)
    for j in range(n):
        w = rec(m,qA)
        if w:
            break
        qA.popleft()            
    if w:
        return "yes"
    else:
        return "no"
    
def rec(m,A):
    Ac = deque(list(A)[:])
    Ad = deque(list(A)[:])
    m_new = m
    if m_new == 0:
        r1 = True
    elif m_new < 0:
        r1 = False
    else:
        if len(A) == 1:
            r1 = False
        else:
            Ac.popleft()
            r1 = rec(m_new,Ac)
    m_new = m - Ad[0]
    if m_new == 0:
        r2 = True
    elif m_new < 0:
        r2 = False
    else:
        if len(A) == 1:
            r2 = False
        else:
            Ad.popleft()
            r2 = rec(m_new,Ad)
    if r1 or r2:
        return True
    else:
        return False

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve(A, ms, flags):
	for i,m in enumerate(ms):
		if m==0:
			flags[i]=True
	if len(A)==0:
		return flags
	else:
		use = solve(A[1:], list(map(lambda x:x-A[0], ms)), flags)
		no_use = solve(A[1:], ms, flags)
		return list(map(lambda x,y:x or y, use, no_use))

def main():
	n = int(input())
	A = input()
	A = list(map(int, A.split()))
	q = int(input())
	m = input()
	m = list(map(int, m.split()))
	flags = [False for i in range(q)]
	for flag in solve(A, m, flags):
		if flag:
			print('yes')
		else:
			print('no')

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

class MyClass():    
    def load(self):
        self.n = input()
        self.A = map(int,raw_input().split())
        self.q = input()
        self.M = map(int,raw_input().split())

    def main(self):
        self.load()
        W = map(self.solve,self.M)
        for w in W:
            print w

    def solve(self,m):
        qA = deque(self.A)
        for j in range(self.n):
            w = self.rec(m,qA)
            if w:
                break
            qA.popleft()            
        if w:
            return "yes"
        else:
            return "no"

    def rec(self,m,A):
        Ac = deque(list(A))
        Ad = deque(list(A))
        m_new = m
        if m_new == 0:
            r1 = True
        elif m_new < 0:
            r1 = False
        else:
            if len(A) == 1:
                r1 = False
            else:
                Ac.popleft()
                r1 = self.rec(m_new,Ac)
        m_new = m - Ad[0]
        if m_new == 0:
            r2 = True
        elif m_new < 0:
            r2 = False
        else:
            if len(A) == 1:
                r2 = False
            else:
                Ad.popleft()
                r2 = self.rec(m_new,Ad)
        if r1 or r2:
            return True
        else:
            return False

if __name__ == "__main__":
    MC = MyClass()
    MC.main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

class MyClass():    
    def load(self):
        self.n = input()
        self.A = map(int,raw_input().split())
        self.q = input()
        self.M = map(int,raw_input().split())

    def main(self):
        self.load()
        W = map(self.solve,self.M)
        for w in W:
            print w

    def solve(self,m):
        qA = deque(self.A)
        for j in range(self.n):
            w = self.rec(m,qA)
            if w:
                break
            qA.popleft()            
        if w:
            return "yes"
        else:
            return "no"

    def rec(self,m,A):
        Ac = deque(list(A))
        Ad = deque(list(A))
        m_new = m
        if m_new < 0:
            r1 = False
        elif m_new == 0:
            r1 = True
        else:
            if len(A) == 1:
                r1 = False
            else:
                Ac.popleft()
                r1 = self.rec(m_new,Ac)
        m_new = m - Ad[0]
        if m_new < 0:
            r2 = False
        elif m_new == 0:
            r2 = True
        else:
            if len(A) == 1:
                r2 = False
            else:
                Ad.popleft()
                r2 = self.rec(m_new,Ad)
        if r1 or r2:
            return True
        else:
            return False
if __name__ == "__main__":
    MC = MyClass()
    MC.main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

class MyClass():    
    def load(self):
        self.n = input()
        self.A = map(int,raw_input().split())
        self.q = input()
        self.M = map(int,raw_input().split())

    def main(self):
        self.load()
        W = map(self.solve,self.M)
        for w in W:
            print w

    def solve(self,m):
        qA = deque(self.A)
        for j in range(self.n):
            w = self.rec(m,list(qA))
            if w:
                break
            qA.popleft()            
        if w:
            return "yes"
        else:
            return "no"

    def rec(self,m,A):
        m_new = m
        if m_new < 0:
            r1 = False
        elif m_new == 0:
            r1 = True
        else:
            if len(A) == 1:
                r1 = False
            else:
                r1 = self.rec(m_new,A[1:])
        m_new = m - A[0]
        if m_new < 0:
            r2 = False
        elif m_new == 0:
            r2 = True
        else:
            if len(A) == 1:
                r2 = False
            else:
                r2 = self.rec(m_new,A[1:])
        if r1 or r2:
            return True
        else:
            return False

if __name__ == "__main__":
    MC = MyClass()
    MC.main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

class MyClass():    
    def load(self):
        self.n = input()
        self.A = map(int,raw_input().split())
        self.q = input()
        self.M = map(int,raw_input().split())

    def main(self):
        self.load()
        W = map(self.solve,self.M)
        for w in W:
            print w

    def solve(self,m):
        qA = deque(self.A)
        for j in range(self.n):
            w = self.rec(m,list(qA))
            if w:
                break
            qA.popleft()
        if w:
            return "yes"
        else:
            return "no"

    def rec(self,m,A):
        if len(A) == 1:
            r1 = False
        else:
            r1 = self.rec(m,A[1:])
        m_new = m - A[0]
        if m_new < 0:
            r2 = False
        elif m_new == 0:
            r2 = True
        else:
            if len(A) == 1:
                r2 = False
            else:
                r2 = self.rec(m_new,A[1:])
        if r1 or r2:
            return True
        else:
            return False

if __name__ == "__main__":
    MC = MyClass()
    MC.main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

class MyClass():    
    def load(self):
        self.n = input()
        self.A = map(int,raw_input().split())
        self.q = input()
        self.M = map(int,raw_input().split())

    def main(self):
        self.load()
        W = map(self.solve,self.M)
        for w in W:
            print w

    def solve(self,m):
        qA = deque(self.A)
        for j in range(self.n):
            w = self.rec(m,list(qA))
            if w:
                break
            qA.popleft()
        if w:
            return "yes"
        else:
            return "no"

    def rec(self,m,A):
        if len(A) == 0:
            return False
        else:
            r1 = self.rec(m,A[1:])
            m_new = m - A[0]
            if m_new < 0:
                r2 = False
            elif m_new == 0:
                r2 = True
            else:
                r2 = self.rec(m_new,A[1:])
            
            if r1 or r2:
                return True
            else:
                return False

if __name__ == "__main__":
    MC = MyClass()
    MC.main()

Submission status: Time Limit Exceeded

Solution code:

def solve(A, ms, flags):
	while 0 in ms:
		i = ms.index(0)
		flags[i]=True
		ms[i]=-1

	if len(A)==0:
		return flags
	else:
		use = solve(A[1:], list(map(lambda x:x-A[0], ms)), flags)
		no_use = solve(A[1:], ms, flags)
		return list(map(lambda x,y:x or y, use, no_use))

def main():
	n = int(input())
	A = input()
	A = list(map(int, A.split()))
	q = int(input())
	m = input()
	m = list(map(int, m.split()))
	flags = [False for i in range(q)]
	for flag in solve(A, m, flags):
		if flag:
			print('yes')
		else:
			print('no')

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
class MyClass():
    def main(self):
        self.n = input()
        self.A = map(int,raw_input().split())
        self.q = input()
        self.M = map(int,raw_input().split())
        
        W = map(self.solve,self.M)
        for w in W:
            print w

    def solve(self,m):
        w = self.rec(m,self.A)
        if w:
            return "yes"
        else:
            return "no"

    def rec(self,m,A):
        if len(A) == 1:
            r1 = False
        else:
            r1 = self.rec(m,A[1:])
        
        m_new = m - A[0]
        if m_new < 0:
            r2 = False
        elif m_new == 0:
            r2 = True
        elif len(A) == 1:
            r2 = False
        else:
            r2 = self.rec(m_new,A[1:])
        
        if r1 or r2:
            return True
        else:
            return False

if __name__ == "__main__":
    MC = MyClass()
    MC.main()

Submission status: Time Limit Exceeded

Solution code:

def solve(A, ms, flags, index):
	now_ms = [m-A[0] for m in ms if m-A[0] >= 0]
	now_index = [i for i,m in zip(index, ms) if m-A[0] >= 0]
	while 0 in now_ms:
		i = now_ms.index(0)
		flags[now_index[i]]=True
		now_index.pop(i)
		now_ms.pop(i)
	
	if len(A)==1:
		return flags
	else:
		use = solve(A[1:], now_ms, flags, now_index)
		no_use = solve(A[1:], ms, flags, index)
		return list(map(lambda x,y:x or y, use, no_use))

def main():
	n = int(input())
	A = input()
	A = list(map(int, A.split()))
	q = int(input())
	m = input()
	m = list(map(int, m.split()))
	flags = [False for i in range(q)]
	index = list(range(q))
	for flag in solve(A, m, flags,index):
		if flag:
			print('yes')
		else:
			print('no')

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
class MyClass():
    def main(self):
        self.n = input()
        self.A = map(int,raw_input().split())
        self.q = input()
        self.M = map(int,raw_input().split())
        
        W = map(self.solve,self.M)
        for w in W:
            print w

    def solve(self,m):
        w = self.rec(m,self.A)
        if w:
            return "yes"
        else:
            return "no"

    def rec(self,m,A):
        if len(A) == 1:
            r1 = False
        else:
            r1 = self.rec(m,A[1:])
        
        m_new = m - A[0]
        if m_new < 0:
            r2 = False
        elif m_new == 0:
            r2 = True
        elif len(A) == 1 or m_new < min(A[1:]):
            r2 = False
        else:
            r2 = self.rec(m_new,A[1:])
        
        if r1 or r2:
            return True
        else:
            return False
    
if __name__ == "__main__":
    MC = MyClass()
    MC.main()

Submission status: Time Limit Exceeded

Solution code:
flags = None
ms = None

def solve(A, index, s):
	s += A[0]
	now_index = [i for i in index if ms[i]>=s and not flags[i]]
	for idx in now_index:
		if ms[idx] == s:
			flags[idx]=True
			now_index.remove(idx)

	if len(A) != 1:
		solve(A[1:], now_index, s)
		solve(A[1:], index, s-A[0])


def main():
	n = int(input())
	A = input()
	A = list(map(int, A.split()))
	q = int(input())
	m = input()
	global ms
	ms = list(map(int, m.split()))
	global flags
	flags = [False for i in range(q)]
	index = list(range(q))
	solve(A, index, 0)
	for flag in flags:
		if flag:
			print('yes')
		else:
			print('no')

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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


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

Submission status: Time Limit Exceeded

Solution code:
def solve(i,m,n):
    if m == 0:
        return True
    if i >= n:
        return False
    if solve(i+1,m,n) == True or solve(i+1,m-A[i],n) == True:
        return True
    else:
        return False
    
n = int(input())
s = input().split(" ")
A = []
for i in range(n):
    A.append(int(s[i]))
q = int(input())
s = input().split(" ")
m = []
for i in range(q):
    m.append(int(s[i]))
for i in range(q):
    if solve(0, m[i], n):
        print("yes")
    else:
        print("no")

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

n = int(input())
A = input()
A = [int(s) for s in A.split()]
q = int(input())
m = input()
m = [int(s) for s in m.split()]

for mm in m:
	ans = 'no'
	for i in range(1,n+1):
		for c in combinations(A,i):
			if sum(c) == mm:
				ans = 'yes'
				break
		if ans == 'yes':
			break
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
def combine(A, m, s):
    for key, a in enumerate(A):
        t = s + a
        if t == m:
            return True
        elif t > m:
            continue
        else:
            if combine(A[key+1:], m, t):
                return True
    return False


if __name__ == "__main__":
    n = input()
    A = [int(a) for a in input().split()]
    q_num = int(input())
    M = [int(q) for q in input().split()]

    total = 0
    chars = 'sum: '
    for m in M:
        print('yes' if combine(A[:], m, 0) else 'no')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2000000)

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

check = True

def exh_search(n, l):
	global check
	if check:
		if(n == 0):
			check = False
		else:
			if len(l) > 1:
				exh_search(n, l[1:])
				if n >= l[0]:
					exh_search(n - l[0], l[1:])
			else:
				if n == l[0]:
					check = False

for x in m:
	check = True
	exh_search(x, a)
	if check:
		print('no')
	else:
		print('yes')

Submission status: Time Limit Exceeded

Solution code:
import sys
import time
sys.setrecursionlimit(2000000)

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

check = True
a.sort(reverse = True)

def exh_search(n, l):
	global check
	if check:
		if n == 0:
			check = False
		else:
			if len(l) > 0:
				exh_search(n, l[1:])
				if n >= l[0]:
					exh_search(n - l[0], l[1:])

for x in m:
	check = True
	exh_search(x, a)
	if check:
		print('no')
	else:
		print('yes')

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 = input()
A = [int(s) for s in A.split()]
q = int(input())
m = input()
m = [int(s) for s in m.split()]

ans = [{True:'yes',False:'no'}[solve(0,mm)] for mm in m]
[print(a) for a in ans]

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 = input()
A = [int(s) for s in A.split()]
q = int(input())
m = input()
m = [int(s) for s in m.split()]

ans = [{True:'yes',False:'no'}[solve(0,mm)] for mm in m]
print('\n'.join(ans))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
????????????
?????? n ?????°??? A ??¨??´??° m ???????????????A ???????´?????????????????????????????´?????¶????????????????
m ???????????????????????????????????????????????°????????????????????????????????????
AA ??????????´???????????????????????????¨?????§????????????

??°??? A ??????????????????????????§???????????¨?????? q ?????? mi ????????????????????§???
???????????????????????? "yes" ????????? "no" ??¨???????????????????????????

n ??? 20 ; q ??? 200 ; 1 ??? A???????´? ??? 2000 ; 1 ??? Mi ??? 2000

"""

def kenzan(m, n, A):
    l = 2 ** n
    for i in range(l):
        mask = 1
        c = 0
        for j in range(n):
            b = i & mask
            if b != 0:
                x = c + A[j]
#                print("{0:2}/{1:2} {6:08b} m[{2:4}] c+Aj[{3:4}] c[{4:4}] Aj[{5:4}]".format(i, mask, m, x, c, A[j], b))
                if x == m:
                    return 0
                elif x > m:
                    break
                else:
                    c = x
            mask <<= 1
    return -1
 
def 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 kenzan(M[i], n, A) == 0:
            print("yes")
        else:
            print("no")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
????????????
?????? n ?????°??? A ??¨??´??° m ???????????????A ???????´?????????????????????????????´?????¶????????????????
m ???????????????????????????????????????????????°????????????????????????????????????
AA ??????????´???????????????????????????¨?????§????????????

??°??? A ??????????????????????????§???????????¨?????? q ?????? mi ????????????????????§???
???????????????????????? "yes" ????????? "no" ??¨???????????????????????????

n ??? 20 ; q ??? 200 ; 1 ??? A???????´? ??? 2000 ; 1 ??? Mi ??? 2000

"""

def kenzan(m, n, A):

    # ?????????????????§????????°???????????£????????????
    nA = []
    max = 0
    min = 2000
    total = 0
    for i in range(n):
        if A[i] == m:
            return 0
        elif A[i] < m:
            nA.append(A[i])
        if max < A[i]:
            max = A[i]
        if min > A[i]:
            min = A[i]
        total += A[i]

    n =len(nA)

    if m > total:
        return -1
    elif m < min:
        return -1

    l = 2 ** n
    for i in range(l):
        mask = 1
        c = 0
        for j in range(n):
            b = i & mask
            if b != 0:
                x = c + nA[j]
#                print("{0:2}/{1:2} {6:08b} m[{2:4}] c+Aj[{3:4}] c[{4:4}] Aj[{5:4}]".format(i, mask, m, x, c, nA[j], b))
                if x == m:
                    return 0
                elif x > m:
                    break
                else:
                    c = x
            mask <<= 1
    return -1
 
def 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 kenzan(M[i], n, A) == 0:
            print("yes")
        else:
            print("no")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
????????????
?????? n ?????°??? A ??¨??´??° m ???????????????A ???????´?????????????????????????????´?????¶????????????????
m ???????????????????????????????????????????????°????????????????????????????????????
AA ??????????´???????????????????????????¨?????§????????????

??°??? A ??????????????????????????§???????????¨?????? q ?????? mi ????????????????????§???
???????????????????????? "yes" ????????? "no" ??¨???????????????????????????

n ??? 20 ; q ??? 200 ; 1 ??? A???????´? ??? 2000 ; 1 ??? Mi ??? 2000

"""
def kenzan(m, n, A):

    if m < A[0]:
        return -1

    # ?????????????????§????????°???????????£????????????
    total = 0
    nA = []
    for i in range(n):
        if A[i] == m:
            return 0
#        print("{} m:{} x:{} total:{}".format(nA,m,A[i], total))
        if A[i] > m:
            break
        nA.append(A[i])
        total += A[i]

    if m > total:
        return -1

    n =len(nA)
    l = 2 ** n
    for i in range(1,l):
        c = 0
        bi = "{0:0<{width}b}".format(i,width=n)
        bi = bi[::-1]
#        print("{0:2}[{1}] m[{2:4}] {3}".format(i, bi,m, n))
        for j in range(n):
#            print("\tj:{} bi:{} Aj[{:4}]".format(j, bi[j], A[j]))
            if bi[j] == "1":
                x = c + nA[j]
#                print("\tm[{:4}] c+Aj[{:4}] c[{:4}] j:{} Aj[{:4}]".format(m, x, c, j, A[j]))
                if x == m:
                    return 0
                elif x > m:
#                    print("BAD")
                    break
                else:
                    c = x
    return -1
 
def main():
    """ ????????? """
    n = int(input())
    A = sorted(map(int,input().split()))
    q = int(input())
    M = list(map(int,input().split()))

    for i in range(q):

        if kenzan(M[i], n, A) == 0:
            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()))
q=int(input())
m=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 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 = 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 M:
    if solve(0, m):
        print('yes')
    else:
        print('no')

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
data = map(int, raw_input().split())
m = int(raw_input())
test = map(int, raw_input().split())

def solve(i,left):
    if left == 0:
        return True
    elif i >= n:
        return False
    return solve(i+1, left) or solve(i+1, left - data[i])

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

Submission status: Time Limit Exceeded

Solution code:
# Aizu Problem ALDS_1_5_A: Exhaustive Search
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")

memo = {}


def solve(A, i, q):
    if q == 0:
        return True
    if i >= n:
        return False
    return solve(A, i + 1, q) or solve(A, i + 1, q - A[i])
    
    
n = int(input())
A = [int(_) for _ in input().split()]
q = int(input())
Q = [int(_) for _ in input().split()]
for q in Q:
    print("yes" if solve(A, 0, q) else "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])

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:
from itertools import combinations as C

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

def check(m):
    for r in range(1, n + 1):
        for sub in C(A, r):
            if sum(sub) == m:
                return True
    return False

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