Subset Sum Problem

Given an array of integers ( A = [a_1, a_2, \dots, a_n] ) and a target sum ( S ), determine whether there exists a non-empty subset of ( A ) whose elements sum exactly to ( S ). In other words, decide if there exists a subset ( I \subseteq {1,2,\dots,n} ) such that [ \sum_{i \in I} a_i = S ] The problem will be given with multiple test cases. For each test case you are given the size ( n ), the target sum ( S ), and the array ( A ). Print "YES" if such a subset exists, otherwise print "NO".

Note: The input is provided via standard input and the output should be written to standard output.

inputFormat

The first line contains a single integer ( T ), the number of test cases. Each test case consists of two lines. The first line of each test case contains two integers ( n ) and ( S ) separated by a space, where ( n ) is the number of elements in the array and ( S ) is the target sum. The second line contains ( n ) integers representing the array elements, separated by spaces.

Example: 2 6 9 3 34 4 12 5 2 5 30 1 3 9 2 5

outputFormat

For each test case, output one line containing either "YES" if there exists a subset whose sum is exactly ( S ), or "NO" if there is no such subset.## sample

2
6 9
3 34 4 12 5 2
5 30
1 3 9 2 5

YES
NO