Subset Sum Problem

Given a list of positive integers and a target sum \(T\), determine whether there exists a subset of the list whose elements add up exactly to \(T\). This is the classic Subset Sum Problem.

You are provided with an integer \(n\), representing the number of elements, and an integer \(T\), the target sum, followed by \(n\) space-separated positive integers. Your task is to print True if such a subset exists and False otherwise.

The problem can be formally defined as: Find if there exists a subset \(S\) of \(\{a_1, a_2, \dots, a_n\}\) such that \[ \sum_{x \in S} x = T \]

This problem can efficiently be solved using dynamic programming for moderate input sizes.

inputFormat

The input is given via standard input (stdin). The first line contains two integers (n) and (T) separated by a space, where (n) is the number of elements and (T) is the target sum. The second line contains (n) positive integers separated by spaces.

outputFormat

Print a single line to standard output (stdout): True if there exists a subset whose sum is exactly (T), otherwise print False.## sample

5 11
2 3 7 8 10

True