Subset Sum Problem

Given an array of integers and a target sum, determine whether there exists a subset of the array that adds up exactly to the target value. Formally, given an array \(A = [a_1, a_2, \dots, a_n]\) and an integer \(T\), decide if there exists a subset \(S \subseteq A\) such that \(\sum_{a \in S} a = T\).

A common approach to solve this problem is using dynamic programming. The recurrence used is:

\(dp[i][j] = dp[i-1][j] \lor \ (a_i \leq j \ \&\& \ dp[i-1][j-a_i])\)

where \(dp[i][j]\) indicates whether a subset of the first \(i\) elements can sum to \(j\). Note that \(dp[i][0] = \text{True}\) for all \(i\) since the empty subset always has a sum of 0.

inputFormat

The input is read from stdin and has the following format:

• The first line contains two integers: \(n\) (the number of elements in the array) and \(T\) (the target sum).
• The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output a single line to stdout containing either "True" if there exists a subset that sums to \(T\), or "False" otherwise.

5 11
2 3 7 8 10

True