Subset Sum Problem

You are given a list of ( n ) integers and an integer ( m ). Your task is to determine whether there exists a subset of the integers that sums exactly to ( m ). Formally, given integers ( a_1, a_2, \ldots, a_n ) and a target value ( m ), decide if there exists a subset ( S \subseteq {1, 2, \ldots, n} ) such that [ \sum_{i \in S} a_i = m, ] where the summation is taken over all indices in ( S ). This problem tests your ability to implement recursive or backtracking algorithms to efficiently search through possible combinations.

inputFormat

The input is given via standard input. The first line contains a single integer ( T ) representing the number of test cases. Each test case is described as follows:

• The first line of each test case contains two integers ( n ) and ( m ), where ( n ) is the number of elements in the list and ( m ) is the target sum.
• The second line contains ( n ) space-separated integers representing the elements of the list.

outputFormat

For each test case, output a single line containing either "YES" if a subset with sum exactly equal to ( m ) exists, or "NO" otherwise. The output should be printed to standard output.## sample

3
5 9
3 34 4 12 5
3 0
7 -3 2
4 15
1 2 3 4

YES
YES
NO