Find a subset of a given set S={sl,s2,  ,sn} of n positive integers whose sum is equal to a given positive integer d. For example, if S={1,2,5,6,8}and d = 9 there are two solutions{1,2,6}and{1,8}.A suitable message is to be displayed if the given problem instance doesn't have a solution.

Given a set of non-negative integers, and a value S, determine if there is a subset of the given set with sum equal to S.

The following paradigm can be used to find the solution of the problem in minimum time: Given a set of non-negative integer, and a value K, determine if there is a subset of the given set with sum equal to K:Group of answer choices

Subset SumMax Score: 150Given a set of non-negative integers, and a value S, determine if there is a subset of the given set with sum equal to S.Input FormatThe first line of the input contains T - the number of test cases. It is followed by 2T lines - the first line of each test case contains N - number of elements in given array and S - the required sum. The second line contains elements of the array.Output FormatFor each test case, print "YES" if there is a subset of the given set with sum equal to given S, otherwise "NO", separated by new line .Constraints30 points1 <= N <= 100 <= S <= 100120 points1 <= N <= 1000 <= S <= 1000General Constraints1 <= T <= 1000 <= A[i] <= 103ExampleInput25 1510 4 5 9 15 1713 11 19 20 21OutputYESNOExplanationExample 1:15 = 9 + 5 + 1Example 2:No such subset exists.

The following paradigm can be used to find the solution of the problem in minimum time: Given a set of non-negative integer, and a value K, determine if there is a subset of the given set with sum equal to K:Group of answer choicesGreedy AlgorithmDivide and ConquerDynamic ProgrammingString Matching

Subset SumProblem Statement:There is a subset A of n positive integers and a value sum. Find whether or not there exists any subset of the given set, the sum of whose elements is equal to the given value of sum.Time complexity of this solution is O(n*sum).Example 1:Input:sum=17 n=4 A[]={2,4,6,9}   Required subset exists subset {2,6,9} has the sum 17 Example 2:Input:sum=17 n=4 A[]={2,4,6,8}  No subset found with required sumYour Task:Write the program to solve this using Dynamic Programming concepts by storing the intermittent results for example for sum=1, sum=2 etc in a matrix to avoid recomputation.