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 M i . 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 ( M i ) are given. Output For each question M i , print yes or no . Constraints  n ≤ 20  q ≤ 200  1 ≤ elements in A ≤ 2000  1 ≤ M i ≤ 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].

Solution (Python):
def recurssion(A, possible, i, sum, size):
    if i == size:
        return
    else:
        possible.add(sum + A[i])
        recurssion(A, possible, i+1, sum, size)
        recurssion(A, possible, i+1, sum + A[i], size)

n = int(input())
A = list(map(int,input().split()))
q = int(input())
aim = list(map(int,input().split()))
possible = set()
recurssion(A, possible, 0, 0, n)
for i in range(q):
    if aim[i] in possible:
        print("yes")
    else:
        print("no")

Solution (Python):
def solve(i, s):
    global A
    global M

    if i < len(A):
        M.add(s + A[i])
        solve(i + 1, s + A[i])
        solve(i + 1, s)


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

solve(0, 0)

q = int(input())

for m in [int(x) for x in input().split()]:
    if m in M:
        print('yes')
    else:
        print('no')

Solution (Python):
import sys, math
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
M = list(map(int, input().split()))
memo = [[None] * 2000 for _ in range(N+1)]

def check(i, m):
    if memo[i][m] is not None:
        return memo[i][m]
    if (m == 0):
        memo[i][m] = True
        return True
    elif (i == N):
        memo[i][m] = False
        return False
    else:
        ans = check(i+1, m) or check(i+1, m - A[i])
        memo[i][m] = ans
        return ans

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

Solution (Python):
import itertools

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

n2=int(input())
B=list(map(int,input().split()))
S=set()
for i in range(1,n+1):
    S=S|set(map(sum,list(itertools.combinations(A,i))))
for j in B:
    if j in S:
        print('yes')
        
    else:print('no')

Solution (Python):
from sys import stdin

def canMake(i, mi):
    global A, dp
    if mi == 0:
        return True
    elif i >= n:
        return False
    else:
        try:
            return dp[(i, mi)]
        except KeyError:
            dp[(i, mi)] = canMake(i+1, mi) or canMake(i+1, mi-A[i])
            return dp[(i, mi)]

n = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
q = int(stdin.readline().rstrip())
m = [int(x) for x in stdin.readline().rstrip().split()]

for mi in m:
    dp = {}
    if canMake(0, mi):
        print("yes")
    else:
        print("no")

Solution (Python):
b = 1
input()
for a in map(int, input().split()):
    b |= b << a
input()
for m in map(int, input().split()):
    print('yes' if (b >> m) & 1 else 'no')

Solution (Python):
n=int(input())
a=list(map(int, input().split()))
m=int(input())
b=list(map(int, input().split()))
d={0:1}
for i in a:
    for j in list(d):
        d[j+i]=1
for i in b:
    if i in d:print('yes')
    else:print('no')

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


def set_possible_m(depth: int, sum: int):
    possible_m[sum] = True

    if depth == n:
        return

    set_possible_m(depth + 1, sum)
    if sum + A[depth] < 2000:
        set_possible_m(depth + 1, sum + A[depth])


possible_m = [False] * 2000
set_possible_m(0, 0)

for mi in M:
    if possible_m[mi]:
        print('yes')
    else:
        print('no')

Solution (Python):
def InputData():
    
    sequence_len = int(input())
    sequence = list(map(int, input().split()))

    description_len = int(input())
    description = list(map(int, input().split()))

    return sequence_len, sequence, description_len, description

def Solve(sequence_num, description_value, sequence, sequence_len):
    if description_value == 0: return True
    elif sequence_num >= sequence_len or description_value > sum(sequence): return False
    res = Solve(sequence_num + 1, description_value, sequence, sequence_len) or \
    Solve(sequence_num + 1, description_value - sequence[sequence_num], sequence, sequence_len)
    
    return res

def main():
    [sequence_len, sequence, description_len, description] = InputData()
    for i in description:
        if Solve(0, i, sequence, sequence_len):
            print("yes")
        else:
            print("no")
        

if __name__ == "__main__":
    main()

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

def com(i, b):
    if b == 0:
        return True
    if i == n or b < 0:
        return False
    if b - sum(a[i:]) > 0:
        return False
    ans = com(i+1, b) or com(i+1, b-a[i])
    return ans

for j in m:
    if com(0, j):
        print('yes')
    else:
        print('no')

Solution (Python):

def selectWhich(A,i,c):
    
    
    
    if c < 1:
        return
    if int(i/c) == 1:
        A.append(1)
        i = i%c
    else:
        A.append(0)
    selectWhich(A,i,c/2)


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

for i in range(2**n):
    l = []
    selectWhich(l,i,2**n)
    tmp = [ x*y for (x,y) in zip(A,l[1:])]
    p.append(sum(tmp))

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

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
M = [0] * q


def check(j, num):
    if m.count(num + A[j]) != 0:
        for k in range(q):
            if num + A[j] == m[k]:
                M[k] = 1
    if j < n - 1:
        check(j+1, num+A[j])
        check(j+1, num)


check(0, 0)
for i in range(q):
    if M[i] == 1:
        print("yes")
    else:
        print("no")

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

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

def dfs(idx, s, target):
    if s == target:
        return 1
    
    if s > target or idx == n:
        return 0
    if s + sum(A[idx:]) < target:
        return 0

    return dfs(idx+1, s, target) or dfs(idx+1, s + A[idx], target)

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

Solution (Python):
import sys
import functools

n = int(sys.stdin.readline())
a = [int(v) for v in sys.stdin.readline().split()]


@functools.lru_cache(maxsize=None)
def solve(k, m):
    if m == 0:
        return True
    if k == n or m < 0:
        return False

    return solve(k + 1, m) or solve(k + 1, m - a[k])


sys.stdin.readline()
for m in map(int, sys.stdin.readline().split()):
    print('yes' if solve(0, m) else 'no')

Solution (Python):






import sys
input = sys.stdin.readline
import cProfile

p = [pow(2,i) for i in range(30)]

def checkSum(l,d,ck=0):
    td = 0
    for i in range(len(l)):
        if  p[i] & ck == p[i]:
            continue
        td += l[i]
    if (td < d):
        return False
    elif ( td == d ):
        return True

    for i in range (len(l)):
        if  p[i] & ck == p[i]:
            continue
        ck += p[i]
        if  checkSum(l,d,ck):
            return True
        d -= l[i]
        
        if d == 0:
            return True
        elif d < 0:
            return False
        if  checkSum(l,d,ck):
            return True
    return False

def main():
    n1 = int(input())
    l1 = list(map(int,input().split()))
    l1.sort()
    l1.reverse()
    n2 = int(input())
    l2 = list(map(int,input().split()))
    for i in range(n2):
        if checkSum(l1,l2[i]):
            print ("yes")
        else:
            print ("no")

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import combinations

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

numbers = set()
for i in range(1, n+1):
    for com in combinations(A, i):
        numbers.add(sum(com))

for j in ms:
    if j in numbers:
        print("yes")
    else:
        print("no")

Solution (Python):
n = int(input())
*A, = map(int, input().split())
q = int(input())
*m, = map(int, input().split())

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

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

Solution (Python):



def ni():
    return list(map(int, input().split()))


def permutation(A, m):
    from itertools import permutations
    for size in range(len(A)):
        for perm in permutations(A, r=size):
            print(perm)
            if sum(perm) == m:
                return True
    return False


def combination(A, m):
    if sum(A) < m:
        return False

    from itertools import combinations
    for size in range(1, len(A)+1):
        
        for comb in combinations(A, size):
            if sum(comb) == m:
                return True

    return False


def solve():
    _ = input()
    A = sorted(ni())
    _ = input()
    mi = ni()

    
    
    

    for m in mi:
        if combination(A, m):
            print('yes')
        else:
            print('no')


if __name__ == '__main__':
    solve()

Solution (Python):
n = int(input())
a_list = list(map(int,input().split()))
q = int(input())
q_list = list(map(int,input().split()))
bits = 1

for a in a_list:
    bits |= bits << a

for q in q_list:
    if (bits>>q)&1:
        print('yes')
    else:
        print('no')

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

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

Solution (Python):
n = int(input())
n_list = list(map(int,input().split()))
q = int(input())
q_list = list(map(int,input().split()))

from functools import lru_cache

@lru_cache(10000)
def solve(i, m):
    if m == 0:
        return True
    if i >= n:
        return False
    res = (solve(i+1, m) | solve(i+1, m-n_list[i]))
    return res


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

Solution (Python):
def judge(data_N,data,data_num,tmp_key,sum_data):
    if(data_N <=data_num):
        return 0
    x=data[data_num]
    if(sum_data[data_num] +x < tmp_key):
        return 0
    if(x==tmp_key):
        return 1
    if(tmp_key <x):
        return 0
    if(judge(data_N,data,data_num+1,tmp_key -x,sum_data)):
        return 1
    if(judge(data_N,data,data_num+1,tmp_key,sum_data)):
        return 1
    return 0

data_N=int(input())
data=list(map(int,input().split()))
data.sort()

tmp_sum=sum(data)
sum_data=[tmp_sum - i for i in data]



key_num=int(input())
keys=list(map(int,input().split()))

for key in keys:
    if(key in data):
        print("yes")
    else:
        if(judge(data_N,data,0,key,sum_data)):
            print("yes")
        else:
            print("no")

Solution (Python):
def solve(i, m, s, memo={}):
    if (i, m) in memo:
        return memo[(i, m)]

    if m == 0:
        memo[(i, m)] = True
        return True

    if m < 0:
        memo[(i, m)] = False
        return False

    if len(s) <= i:
        return False

    ret = solve(i+1, m, s, memo) or solve(i+1, m-s[i], s, memo)
    memo[(i, m)] = ret

    return ret

def main():
    _ = input()
    ss = [int(x) for x in input().split(' ')]

    _ = input()
    ms = [int(x) for x in input().split(' ')]

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

if __name__ == '__main__':
    main()

Solution (Python):


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


dp = [[None]*(max(M)+1) for i in range(n)]


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

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

Solution (Python):
import sys
import itertools

n=int(sys.stdin.readline())
A = [int(i) for i in sys.stdin.readline().split()]
sys.stdin.readline()
AA=[]
for l in range(1,n+1):
    for i in itertools.combinations(A, l):
        AA.append(sum(i))

for i in sys.stdin.readline().split():
    if int(i) in AA:
        print('yes')
    else:
        print('no')

Solution (Python):
n = int(input())
*A, = map(int,input().split())
q = int(input())
*ms, = map(int, input().split())

def solve(ind, cur):
    if cur == 0:
        return True
    if ind >= n:
        return False

    return solve(ind + 1, cur) or solve(ind + 1, cur - A[ind])

amax = sum(A)
amin = min(A)
for m in ms:
    if amax < m or amin > m: print('no')
    else:
        if solve(0, m): print('yes')
        else: print('no')

Solution (Python):
def solve(i,m):
    if m == 0:
        return True
    if i >= n:
        return False
    res = solve(i+1,m) or solve(i+1,m-S[i])
    return res
    
n = int(input())
S = list(map(int, input().split()))
int(input())
T = list(map(int, input().split()))

for i in T:
    if   i > sum(S):
        print("no")
    else:
        print("yes" if solve(0,i) else "no")

Solution (Python):
import sys
import collections


sys.setrecursionlimit(1000000)


def li_input():
    return [int(_) for _ in input().split()]

def to_bin(k):
    return bin(k)[2:]


def main():
    N = int(input())
    A = li_input()
    M = int(input())
    Q = li_input()

    B = []
    D = collections.defaultdict(lambda: 0)

    for i in range(2 ** len(A)):
        b = to_bin(i)

        if len(b) < len(A):
            b = "0" * (len(A) - len(b)) + b
        
        B.append(b)

    for b in B:
        s = 0
        for i,is_add in enumerate(b):
            if is_add == "1":
                s += A[i]

        D[s] = 1
    
    for q in Q:
        if D[q] == 1:
            print("yes")
        else:
            print("no")
            


main()

Solution (Python):
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")

Solution (Python):
import sys
import math

f = sys.stdin
n = int(f.readline().split()[0])
A = list(map(int, f.readline().split()[:n]))
sumA = sum(A)
minA = min(A)
A.sort()
q = int(f.readline().split()[0])
M = list(map(int, f.readline().split()[:q]))


def check(p, t):
    global A, sumA, minA
    if t == 0:
        return True
    if minA > t or sumA < t:
        return False
    elif t < 0 or p > len(A) - 1:
        return False
    if check(p + 1, t - A[p]):
        return True
    return check(p + 1, t)


for ele in M:
    if minA == ele or sumA == ele:
        print("yes")
    elif check(0, ele):
        print("yes")
    else:
        print("no")

Solution (Python):
n=int(input())
A=[int(i) for i in input().split()]
m=int(input())
B=[int(i) for i in input().split()]

for i in range(len(B)):
    C=[[0 for j in range(B[i]+1)]for k in range(len(A)+1)]
    for j in range(1,len(A)+1):
        for k in range(1,B[i]+1):
            if A[j-1]<=k:
                C[j][k]=max(C[j-1][k-A[j-1]]+A[j-1],C[j-1][k])
            else:
                C[j][k]=C[j-1][k]

    if C[len(A)][B[i]]==B[i]:
        print("yes")
    else:
        print("no")

Solution (Python):
n=int(input())
A=list(map(int,input().split()))
m=int(input())
B=list(map(int,input().split()))

def ES(x,y):
  if x==n: S[y]=1
  else:
    ES(x+1,y)
    if y+A[x]<=2000:
      ES(x+1,y+A[x])
     
S=[0 for i in range(2001)]
ES(0,0)
for i in range(m):
  if S[B[i]]==1: print("yes")
  else: print("no")

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
b = set()
for i in range(2**n):
  t = 0
  for j in range(n):
    if i>>j&1:
      t += a[j]
  b.add(t)
for ele in m:
  if ele in b:
    print("yes")
  else:
    print("no")

Solution (Python):

s=set({})
n=int(input())
a=list(map(int,input().split()))
def check(i,sm):
    if i==n:
        s.add(sm)
        return
    check(i+1,sm+a[i])
    check(i+1,sm)
check(0,0)
input()
for i in map(int,input().split()):
    if i in s:
        print('yes')
    else:
        print('no')

Solution (Python):
canmake = [False for _ in range(2001)]
n = int(input())
A = [int(s) for s in input().split()]
q = int(input())
M = [int(s) for s in input().split()]
for a in A:
	for num in range(2000-a,0,-1):
		if canmake[num]: canmake[a+num] = True
	canmake[a] = True
for m in M:
	if canmake[m]: print('yes')
	else: print('no')