Subset Sum Problem

Given an array of integers and a target sum, determine whether there exists a subset of the array whose elements sum up exactly to the target. This problem can be solved using dynamic programming. The recurrence relation is given by: $$dp[i] = dp[i] \lor dp[i - \text{num}]$$ for every number in the array, with the initial state $$dp[0] = \text{True}$$.

inputFormat

The input is read from standard input. The first line contains an integer T, the number of test cases. For each test case, the first line contains two integers: N, the number of elements in the array, and S, the target sum. The following line contains N space-separated integers representing the array elements.

outputFormat

For each test case, output a single line: 'True' if there exists a subset that sums up to the target S, otherwise 'False'.## sample

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

True
False