Subset Sum Problem

The Subset Sum Problem is a classical decision problem in computer science. Given an array of integers \(A = [a_1, a_2, \ldots, a_n]\) and a target sum \(T\), your task is to determine whether there exists a subset \(S \subseteq A\) such that the sum of its elements equals \(T\). For example, if \(A = [3, 34, 4, 12, 5, 2]\) and \(T = 9\), the answer is True because \(4 + 5 = 9\).

The problem can be solved using dynamic programming. One common approach is to use a boolean array \(dp\) where \(dp[j]\) indicates whether a sum of \(j\) can be formed by some subset of the array. The recurrence is given by:

[ dp[j] = dp[j] \vee dp[j - a_i] \quad \text{for each } a_i \in A \text{ and } j \geq a_i. ]

Implement a program that reads the list of numbers and target from standard input and outputs True if such a subset exists, otherwise False.

inputFormat

The first line of the input contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers representing the array elements. The third line contains an integer \(T\) representing the target sum.

outputFormat

Output a single line containing either True if there exists a subset whose sum equals \(T\), or False otherwise.

6
3 34 4 12 5 2
9

True