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 problem is asking to determine if there is a subset of a given set of non-negative integers that sums up to a specific value S.

Here is a step-by-step solution using dynamic programming:

1. Initialize a boolean 2D array dp[N+1][S+1], where N is the number of elements in the given array and S is the required sum. The size of the array is N+1 and S+1 to account for the base case when N or S is 0.

2. Set dp[i][0] = True for all i from 0 to N, because there is always a subset (empty set) with sum 0.

3. Set dp[0][j] = False for all j from 1 to S, because there is no subset with sum j when the number of elements is 0.

4. For i from 1 to N and j from 1 to S, do the following:

   • If the current element is less than or equal to the current sum, set dp[i][j] = dp[i-1][j] || dp[i-1][j-A[i-1]], where A is the given array. This means we can either include the current element in the subset or exclude it.
   • If the current element is greater than the current sum, set dp[i][j] = dp[i-1][j]. This means we can't include the current element in the subset because it's greater than the current sum.

5. The answer will be dp[N][S]. If dp[N][S] is True, print "YES". Otherwise, print "NO".

This solution works because it explores all possible subsets and sums, and stores the results in a 2D array. The time complexity is O(N*S), which is feasible when N and S are up to 1000.

The problem is asking to determine if there is a subset of a given set of non-negative integers that sums up to a specific value S.

Here is a step-by-step solution using dynamic programming:

1. Initialize a boolean 2D array dp[N+1][S+1], where N is the number of elements in the array and S is the required sum. The size of the array is N+1 and S+1 to account for the base case when N or S is 0.

2. Set dp[i][0] = True for all i from 0 to N. This represents the case when the required sum is 0. For any number of elements, there is always a subset (empty subset) with sum 0.

3. Set dp[0][j] = False for all j from 1 to S. This represents the case when the number of elements is 0. If there are no elements, we can't form a subset with sum greater than 0.

4. For i from 1 to N and j from 1 to S, do the following:

   • If the current element is greater than the current sum, then we can't include this element in the subset. So, dp[i][j] = dp[i-1][j].
   • If the current element is less than or equal to the current sum, then we have two options: either include this element in the subset or don't include it. So, dp[i][j] = dp[i-1][j] || dp[i-1][j - arr[i-1]], where arr[i-1] is the current element.

5. After filling up the dp array, the answer will be dp[N][S]. If dp[N][S] is True, print "YES". Otherwise, print "NO".

This solution works in O(NS) time and O(NS) space.

Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol Sol