Subset Sum Problem

Given a set of weights, determine whether there exists a subset of these weights whose sum is exactly equal to a given target value. Formally, given a list of integers w and an integer T, decide if there is a subset S such that

$$\sum_{i \in S} w_i = T$$

Note that the empty subset is considered to have a sum of 0.

inputFormat

The first line of input contains two integers n and T where n is the number of weights and T is the target sum. The second line contains n space-separated integers representing the weights.

outputFormat

Output a single line with either "True" if there exists a subset whose sum equals T, or "False" otherwise.

4 5
1 3 9 2

True