Subset Sum Problem

You are given several test cases. In each test case, you are given a list of non-negative integers and a target value \(T\). Your task is to determine if there is any subset of the list of integers that sums exactly to \(T\).

More formally, given a sequence \(a_1, a_2, \dots, a_n\) and an integer target \(T\), decide whether there exists a subset \(S \subseteq \{1,2,\dots,n\}\) such that \(\sum_{i \in S} a_i = T\). If such a subset exists, print YES; otherwise, print NO.

This is a classic problem that can be solved using dynamic programming.

inputFormat

The first line contains an integer \(Q\) representing the number of test cases. Each test case is described as follows:

• The first line contains an integer \(n\), the number of elements in the list.
• The second line contains \(n\) space-separated integers.
• The third line contains an integer \(T\), the target sum.

Note: When \(n = 0\) the list is empty.

outputFormat

For each test case, output a single line with either YES if there exists a subset whose sum is exactly \(T\), or NO otherwise.

## sample

3
5
2 3 7 8 10
10
4
1 2 4 8
15
3
1 1 1
5

YES
YES
NO

</p>