Help me in solving A1 problem

help
,
1

My issue

I would like to know how to apply dynamic programming technique on this question.

My code

# cook your dish here
def subset(lst,target):
    if target in lst:
        return True
    
    else:
        for i in range(len(lst)):
            if subset(lst[i+1:],target-lst[i]):
                return True
                
    return False
            
T=int(input())
for i in range(T):
    N,M=[int(j) for j in input().split()]
    res=[None for j in range(N)]
    banknote=[int(input()) for j in range(N)]
    if subset(banknote,M):
        print('Yes')
    else:
        print('No')

Problem Link: A1 Problem - CodeChef

2

@harry_duan
Its a simple subset sub dp problem . U can find relevant articles by searching subset sum dp.
and in case u want c++ code , i can help u with that .

3

Thanks for your reply, but the situation is that now my program could work by using a recursive function; however, one of the tag for this question is dynamic programming, so I would like to know if there is any way we can apply dynamic programming to it.

4

@harry_duan
U can use memoization to convert recursion to dp solution .
Just google it u will find the relevant articles regarding that.