Taco Subset Sum Problem

You are given a list of positive integers and a target value \(T\). Your task is to determine whether any combination of elements from the list (each used at most once) can sum exactly to \(T\). This is a classic subset sum problem that can be solved using dynamic programming.

We define a boolean array \(dp\) of size \(T+1\) where \(dp[i]\) is true if there exists a subset of the given numbers that sums to \(i\). The recurrence relation is given by:

\(dp[i] = dp[i] \vee dp[i - num]\) for any \(num\) in the list and for every \(i \geq num\).

Print True if there exists such a subset, and False otherwise.

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains two integers \(n\) and \(T\), where \(n\) is the number of elements and \(T\) is the target sum.
• The second line contains \(n\) positive integers separated by spaces.

outputFormat

Output a single line to standard output (stdout) with either True or False indicating whether there exists a subset of the given numbers that sums exactly to \(T\).

5 11
2 3 7 8 10

True