Problem:


Exhaustive Search

Write a program which reads a sequence A of n elements and an integer M, and outputs "yes" if you can make M by adding elements in A, otherwise "no". You can use an element only once.

You are given the sequence A and q questions where each question contains Mi.

Input

In the first line n is given. In the second line, n integers are given. In the third line q is given. Then, in the fourth line, q integers (Mi) are given.

Output

For each question Mi, print yes or no.

Constraints

n ≤ 20

 q ≤ 200 

1 ≤ elements in A ≤ 2000

1 ≤ Mi ≤ 2000

Sample Input 1

5
1 5 7 10 21
8
2 4 17 8 22 21 100 35

Sample Output 1

no
no
yes
yes
yes
yes
no
no

Notes

You can solve this problem by a Burte Force approach. Suppose solve(p, t) is a function which checkes whether you can make t by selecting elements after p-th element (inclusive). Then you can recursively call the following functions:

solve(0, M) 

solve(1, M-{sum created from elements before 1st element}) 

solve(2, M-{sum created from elements before 2nd element}) 

...

The recursive function has two choices: you selected p-th element and not. So, you can check solve(p+1, t-A[p]) and solve(p+1, t) in solve(p, t) to check the all combinations.

For example, the following figure shows that 8 can be made by A[0] + A[2].

Template in C
-->



Sample input:
5
1 5 7 10 21
8
2 4 17 8 22 21 100 35


Sample output:
no
no
yes
yes
yes
yes
no
no

Submission status: Accepted

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

B = []
C = []
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.append(sum(C0))

for j, r in enumerate(q):    
    if  r in C:
        ans[j] = "yes"

print(*ans, sep="\n")

Submission status: Accepted

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

R = [[None] * 2000 for i in range(n+1)]
def solve(A, n, i, m):
    if R[i][m] != None:
        return R[i][m]
    if m == 0:
        R[i][m] = True
        return True
    if n <= i:
        R[i][m] = False
        return False
    a = A[i]
    R[i][m] = (solve(A, n, i+1, m) or solve(A, n, i+1, m - a))
    return R[i][m]

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

Submission status: Accepted

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.combinations(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:
import itertools as it
    
n = int(input())
A = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))

s = set()

for i in range(n):
    li= list(it.combinations(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:
input()
nlist=map(int, raw_input().split())
input()
qlist=map(int, raw_input().split())

n = len(nlist)

dic = {}

def func(idx, m):
    
    try:
        return dic[m][idx]
    except:
        pass

    if m==0:
        tmp=dic.get(m,{})
        tmp.update({idx: True})
        dic.update({m:tmp})
    elif idx > n-1:
        tmp=dic.get(m,{})
        tmp.update({idx: False})
        dic.update({m:tmp})
        
    elif func(idx+1, m):
        tmp=dic.get(m,{})
        tmp.update({idx: True})
        dic.update({m:tmp})
    elif func(idx+1, m-nlist[idx]):
        tmp=dic.get(m,{})
        tmp.update({idx: True})
        dic.update({m:tmp})
    else:
        tmp=dic.get(m,{})
        tmp.update({idx: False})
        dic.update({m:tmp})
        
    return dic[m][idx]


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

Submission status: Accepted

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

record = [False] * 2000


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 array_1:
        # record[i] = True
        for j in range(2000 - i, 0, -1):
            if record[j]:
                # print(j, i + j)
                record[i + j] = True
        record[i] = True

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


if __name__ == '__main__':
    solution()

Submission status: Accepted

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

"""
from itertools import combinations

if __name__ == '__main__':
    # ??????????????\???
    num1 = int(input())
    M = [int(x) for x in input().split(' ')]
    num2 = int(input())
    A = [int(x) for x in input().split(' ')]
    #A = [1, 5, 7, 10, 21]
    #pick = 4
    #M = [2, 4, 17, 8]

    # ????????????
    results = ['no' for x in range(len(A))]

    for p in range(1, len(M)+1):
        combi = combinations(M, p)
        for choice in combi:
            total = sum(choice)
            if total in A:
                while total in A:
                    i = A.index(total)
                    results[i] = 'yes'
                    A[i] = 'Done'

    # ???????????????
    for txt in results:
        print(txt)

Submission status: Accepted

Solution code:
from itertools import combinations

if __name__ == '__main__':
    # ??????????????\???
    num1 = int(input())
    A = [int(x) for x in input().split(' ')]
    num2 = int(input())
    M = [int(x) for x in input().split(' ')]
    #A = [1, 5, 7, 10, 21]
    #pick = 4
    #M = [2, 4, 17, 8]

    # ????????????
    results = ['no' for x in range(len(M))]  # M?????¨??????????´?????????????????????????????????§????????????????????±???(no)??¨????????????

    for p in range(1, len(A)+1):  # A????????????1????????¨????????°?????????????????¢????????????
        combi = combinations(A, p)  # n??????????????¢??????????????´????????¨?????????????????????
        for choice in combi:
            total = sum(choice)
            while total in M:
                i = M.index(total)
                results[i] = 'yes'
                M[i] = 'Done'

    # ???????????????
    for txt in results:
        print(txt)

Submission status: Accepted

Solution code:
import sys

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

q = int(input())
M = [int(m) for m in input().split()]

makable = set()

for i in range(2 ** n):
    total = 0

    for j in range(n):
        b = i % 2
        total += A[j] * b
        i //= 2

    makable.add(total)

# print(makable)

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

Submission status: Accepted

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

    def solve(self, tgt):
        self.tgt = tgt
        self.history = (self.max_depth+1)*[4000 * [None]]
        self.history = [[None for i in range(4000)] for x in range(self.max_depth + 1)]
        if self._rec_solve(0, 0):
            return 'yes'
        else:
            return 'no'

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


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 val in m_ary:
        print(s.solve(val))

Submission status: Accepted

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

n2 = 2**n
aa = [0 for _ in range(n2)]
for i in range(n):
    t = 2**i
    for j in range(n2):
        if (j//t)%2:
            aa[j] += a[i]
aa = set(aa)

for k in m:
    if k in aa:
        print('yes')
    else:
        print('no')

Submission status: Accepted

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

n2 = 2**n
aa = [0 for _ in range(n2)]
for i in range(n):
    t = 2**i
    for j in range(n2):
        if (j//t)%2:
            aa[j] += a[i]

for k in m:
    if k in aa:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
memo = {}
def solve(p, t):
  key = "{}:{}".format(p, t)
  if key in memo: return memo[key]
  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):
    memo["{}:{}".format(p + 1, t)] = True
    return True
  else:
    memo["{}:{}".format(p + 1, t)] = False
    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: Accepted

Solution code:
from sys import stdin, stderr
from functools import lru_cache

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

    return rec(i - 1, m) or rec(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(n - 1, m):
        print('yes')
    else:
        print('no')

Submission status: Accepted

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_sum.pop(0)

A.reverse()
A_sum.reverse()


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

def search(base, m, n):
    if base == m:
        return True
    if len(A)-1 < n or m - base > A_sum[n]:
        return False
    result = False
    for i in range(len(A)-1,n-1,-1):
        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: Accepted

Solution code:
import sys
import itertools

def can_be_composed(n, min_list, max_list, m, A):
	for i in range(1, n + 1):
		if m < min_list[i - 1]:
			continue
		if m > max_list[i - 1]:
			continue

		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()))
A.sort()
q = int(fin.readline())
m_list = list(map(int, fin.readline().split()))

min_list = [0]
min_list[0] += A[0]
for i in range(1, n):
	min_list.append(min_list[i - 1] + A[i])

max_list = [0]
max_list[0] += A[n - 1]
for i in range(1, n):
	max_list.append(max_list[i - 1] + A[n - i - 1])

for m in m_list:
	if can_be_composed(n, min_list, max_list, m, A):
		print("yes")
	else:
		print("no")

Submission status: Accepted

Solution code:
import sys
#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:
	can_compose = False
	s = [[] for i in range(n)] #s[i][m]??§???A[i]?????§???????´???§m????????????????????????????????????
	for i in range(n):
		s[i] = [False for i in range(m + 1)]

	for j in range(m + 1):
		if j == A[0]:
			s[0][j] = True
		else:
			s[0][j] = False
		
	if s[0][m]:
		can_compose = True
		
	if not can_compose:
		for i in range(1, n):
			for j in range(m + 1):
				if j == A[i]:
					s[i][j] = True
				elif s[i - 1][j]:
					s[i][j] = True
				else:
					if j - A[i] >= 0:
						s[i][j] = s[i - 1][j - A[i]]
			
			if s[i][m]:
				can_compose = True
				break

	if can_compose:
		print("yes")
	else:
		print("no")

Submission status: Accepted

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

d = {}
def solve(i,s):
    if i == len(A):
        d[s] = 0
        return s
        
    solve(i+1,s)
    solve(i+1,s+A[i])
    return 1

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

Submission status: Accepted

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

def makeSum(A,i,T):
    if i == len(A):
        T[sum(A)] = 0
    else:
        makeSum(A,i+1,T)
        ret = A[i]
        A[i] = 0
        makeSum(A,i+1,T)
        A[i] = ret

T = {}
makeSum(A,0,T)
for m in M:
    if m in T:
        print("yes")
    else:
        print("no")

Submission status: Accepted

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

max = sum(b) + 1
for tt in t:
    print 'yes' if tt < max and True == solve(0, tt, b) else 'no'

Submission status: Accepted

Solution code:
import itertools

numA = int(input().rstrip())
listA = list(map(int,input().rstrip().split(" ")))
numQ = int(input().rstrip())
listQ = list(map(int,input().rstrip().split(" ")))

sumA = []
cnt = 0


for i in range(1,numA+1):
    tmpComb = list(itertools.combinations(listA, i))
    for nums in tmpComb:
        sumA.append(sum(nums))


for i in range(numQ):
    if sumA.count(listQ[i]) > 0:
        print("yes")
    else:
        print("no")

Submission status: Accepted

Solution code:
import itertools
 
numA = int(input().rstrip())
listA = list(map(int,input().rstrip().split(" ")))
numQ = int(input().rstrip())
listQ = list(map(int,input().rstrip().split(" ")))
 
sumA = set([])
cnt = 0
 
 
for i in range(1,numA+1):
    tmpComb = list(itertools.combinations(listA, i))
    for nums in tmpComb:
        sumA.add(sum(nums))
 
 
for i in range(numQ):
    if listQ[i] in sumA:
        print("yes")
    else:
        print("no")

Submission status: Accepted

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

import random
import sys
import os
import pprint

#fd = os.open('ALDS1_5_A.txt', os.O_RDONLY)
#os.dup2(fd, sys.stdin.fileno())

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

# memo table T[i][m]
row_num = len(A)
column_num = 2000
T = [[None for i in range(column_num)] for j in range(row_num)]
#pprint.pprint(T)


def solve(i, m):
    # out of index
    if i >= len(A):
        return False
    if m < 0:
        return False

    if T[i][m] is not None:
        return T[i][m]

    if m == 0:
        T[i][m] = True
    elif m == A[i]:
        T[i][m] = True
    #elif i >= len(A):
    #    T[i][m] = False
    elif solve(i+1, m):
        T[i][m] = True
    elif solve(i+1, m - A[i]):
        T[i][m] = True
    else:
        T[i][m] = False
    return T[i][m]

test_num = int(input())
test_values = map(int, input().split())
for v in test_values:
    result = solve(0, v)
    if result is True:
        print('yes')
    else:
        print('no')

Submission status: Accepted

Solution code:
def solve():
    def dfs(idx, end, value, is_make):
        if idx == end:
            if value > 2000:
                return
            
            is_make[value] = True
            return

        dfs(idx + 1, end, value + A[idx], is_make)
        dfs(idx + 1, end, value, is_make)

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

    is_make = [False] * (2000 + 1)
    dfs(0, n, 0, is_make)

    for m in M:
        print('yes' if is_make[m] else 'no')

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
N = int(2**n)
d = []

for i in range(N):
    b = "{:0{}b}".format(i, n)
    d.append(sum(A[j] for j in range(n) if b[j] == '1'))

    #print(b)

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

Submission status: Accepted

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

# i x m matrix
memo = [[None for i in range(2000)] for j in range(n + 1)]

def solve(i, m):
    if memo[i][m] is not None:
        return memo[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:
            memo[i][m] = True
            return True
        else:
            memo[i][m] = False
            return False


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

Submission status: Accepted

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


def check_solvable_recursively(number, is_solvable, candidate_numbers):
    """exhaustively search representable as summation of numbers in candidate_numbers

    Args:
        number: representable number
        is_solvable: is solvable list
        candidate_numbers: candidate numbers to be used

    Returns:
        None
    """
    is_solvable[number] = True
    if candidate_numbers:
        check_solvable_recursively(number + candidate_numbers[0], is_solvable, candidate_numbers[1:])
        check_solvable_recursively(number, is_solvable, candidate_numbers[1:])
    else:
        pass


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

    is_solvable_list = [False] * 2001

    check_solvable_recursively(0, is_solvable_list, candidate_numbers)

    for target_number in target_number_list:
        if is_solvable_list[target_number]:
            print "yes"
        else:
            print "no"

if __name__ == "__main__":
    main()

Submission status: Accepted

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


def check_solvable_recursively(number, is_solvable, candidate_numbers):
    """exhaustively search representable as summation of numbers in candidate_numbers

    Args:
        number: representable number
        is_solvable: is solvable list
        candidate_numbers: candidate numbers to be used

    Returns:
        None
    """
    if not is_solvable[number]:
        is_solvable[number] = True
    if candidate_numbers:
        check_solvable_recursively(number + candidate_numbers[0], is_solvable, candidate_numbers[1:])
        check_solvable_recursively(number, is_solvable, candidate_numbers[1:])


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

    is_solvable_list = [False] * 2001

    check_solvable_recursively(0, is_solvable_list, candidate_numbers)

    for target_number in target_number_list:
        if is_solvable_list[target_number]:
            print "yes"
        else:
            print "no"

if __name__ == "__main__":
    main()

Submission status: Accepted

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


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

    representable_number_set = {0}
    for candidate_number in candidate_number_list:
        for num in representable_number_set.copy():
            representable_number_set.add(num + candidate_number)

    for target_number in target_number_list:
        if target_number in representable_number_set:
            print "yes"
        else:
            print "no"

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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]

  if mi <= sumA:
    f(A, mi, res)

  if res[0]:
    print("yes")
  else:
    print("no")

Submission status: Accepted

Solution code:
n= int(input())
A = list(map(int, input().split()))
q = int(input())
Mi = map(int, input().split())
PS={}
def solve(i,m):
 if m == 0:
  return True
 if (i,m) in PS:
  return PS[(i,m)]
 if i >= n:
  return False
 res = solve(i+1, m) or solve(i + 1, m - A[i])
 PS[(i,m)] = res
 return res

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

Submission status: Accepted

Solution code:
# coding=utf-8

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

n = int(input())
A = tuple(map(int, input().split()))
q = int(input())
M = tuple(map(int, input().split()))
sum_A = sum(A)

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

Submission status: Accepted

Solution code:
# coding=utf-8

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

n = int(input())
A = tuple(map(int, input().split()))
q = int(input())
M = tuple(map(int, input().split()))
sum_A = sum(A)
ever_calc = [[None] * 2000 for i in range(n+1)]

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

Submission status: Accepted

Solution code:
# coding=utf-8

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

n = int(input())
A = tuple(map(int, input().split()))
q = int(input())
M = tuple(map(int, input().split()))
sum_A = sum(A)
ever_calc = [[None] * 2000 for i in range(n+1)]

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

Submission status: Accepted

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 = True
        elif len(A) > 1 and min(A[1:]) <= m_new <= sum(A[1:]):
            r2 = self.rec(m_new,A[1:])
        else:
            r2 = False

        if r1 or r2:
            return True
        else:
            return False

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

Submission status: Accepted

Solution code:
from itertools import chain, combinations

def power_set(x):
	return chain.from_iterable(combinations(x, r) for r in range(len(x)+1))

def main():
	n = int(input())
	A = input()
	#print(n)
	A = list(map(int, A.split()))
	q = int(input())
	m = input()
	ms = list(map(int, m.split()))
	powerset = power_set(A)
	sum_set = [sum(s) for s in powerset if len(s)!=0]
	
	for m in ms:
		if m in sum_set:
			print('yes')
		else:
			print('no')

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def power_set(A, s):
	if len(A) == 0:
		return {s}
	else:
		return power_set(A[1:], s) | power_set(A[1:], s+A[0])

def main():
	n = int(input())
	A = input()
	#print(n)
	A = list(map(int, A.split()))
	q = int(input())
	m = input()
	ms = list(map(int, m.split()))
	powerset = power_set(A, 0)
	
	for m in ms:
		if m in powerset:
			print('yes')
		else:
			print('no')

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from collections import deque

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

    p = rec([0],A)

    for m in M:
        if m in p:
            print "yes"
        else:
            print "no"

def rec(a,A):
    if len(A) == 0:
        return a
    else:
        y = A.popleft()
        a = a+[x+y for x in a]
        return rec(a,A)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
A = tuple(map(int,input().split()))
q = int(input())
Q = tuple(map(int, input().split()))
dp = [0]*(2**n)

for i in range(n):
    for j in range(1<<i):
        dp[j+(1<<i)] = dp[j] + A[i]

s = set(dp)
for n in Q:
    print("yes" if set([n]) & s else "no")

Submission status: Accepted

Solution code:
import bisect
n = int(input())
A = tuple(map(int,input().split()))
q = int(input())
Q = tuple(map(int, input().split()))
dp = [0]*(2**n)

for i in range(n):
    for j in range(1<<i):
        dp[j+(1<<i)] = dp[j] + A[i]
dp.sort()

for n in Q:
    i = bisect.bisect(dp, n)
    print("yes" if i>0 and n==dp[i-1] else "no")

Submission status: Accepted

Solution code:
import itertools


def rev(x):
    return sumA - x


if __name__ == "__main__":
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    M = list(map(int, input().split()))
    sumA = sum(A)
    all_sum = set()
    for i in range((n+1)//2):
        com = set(itertools.combinations(A, i+1))
        com_sum = set(map(sum, com))
        com_sum_rev = set(map(rev, com_sum))
        all_sum = all_sum.union(com_sum)
        all_sum = all_sum.union(com_sum_rev)
    for m in M:
        if m in all_sum:
            print("yes")
        else:
            print("no")

Submission status: Accepted

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 = []
s = sum(A)
for mm in m:
	if s < mm:
		ans.append('no')
	else:
		ans.append({True:'yes',False:'no'}[solve(0,mm)])
#ans = [{True:'yes',False:'no'}[solve(0,mm)] for mm in m]
print('\n'.join(ans))

Submission status: Accepted

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 main():
    """ ????????? """
    n = int(input())
    A = sorted(map(int,input().split()))
    q = int(input())
    M = list(map(int,input().split()))
    g = 0

    tA = []
    l = 2 ** n
    for i in range(1,l):
        c = 0
        bi = "{0:0{width}b}".format(i,width=n)
        bi = bi[::-1]
        for j in range(n):
            if bi[j] == "1":
                c += A[j]
        tA.append(c)
#    tA.sort()

    for mi in M:
        if mi in tA:
            print("yes")
        else:
            print("no")

if __name__ == '__main__':
    main()

Submission status: Accepted

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

bits = 1
for a in A:
    bits |= bits << a

for q in Q:
    print("yes"*((bits >> q) & 1)or"no")

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
readline()
bits = 1
for a in map(int, readline().split()): bits |= bits << a
readline()
sys.stdout.write("\n".join("yes"*((bits >> q) & 1)or"no" for q in map(int, readline().split())))
sys.stdout.write("\n")

Submission status: Accepted

Solution code:
input()
bits = 1
for a in map(int, input().split()): bits |= bits << a
input()
print(*("yes"*((bits >> q) & 1)or"no" for q in map(int, input().split())), sep='\n')

Submission status: Accepted

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

memo = {}
def solve(i, m):
    if m == 0:
        return True
    if i >= n:
        return False
    if memo.get((i, m), None) == None:
        memo[(i, m)] = solve(i + 1, m) or solve(i + 1, m - A[i])
    return memo[(i, m)]
for m in M:
    if solve(0, m):
        print('yes')
    else:
        print('no')

Submission status: Accepted

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'

a = [0]
for i in range(n):
    a = a + [a[j] + data[i] for j in range(len(a))]

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
A = [int(n) for n in input().split()]
q = int(input())
M = [int(n) for n in input().split()]

numbers = [0]

for a in A:
    numbers = numbers + [n+a for n in numbers]

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

sum_list = []
for i in range(2**n):
    b = '{0:0{1}b}'.format(i, n)

    temp = []
    for j in range(n):
        if b[j] == '1':
            temp.append(A[j])
    sum_list.append(sum(temp))

for k in m:
    print('yes' if k in sum_list else 'no')