Subset Sum Problem

Given an array of integers \(A\) and a target integer \(T\), determine whether there exists a subset of \(A\) whose sum equals \(T\). You may choose any number of elements (including none or all) from the array to form the subset. An effective approach is to iteratively build the set of all achievable subset sums. This problem can be solved using dynamic programming techniques.

inputFormat

The input is provided via standard input (stdin) and consists of three lines:

1. The first line contains an integer \(n\) representing the number of elements in the array.
2. The second line contains \(n\) space-separated integers, which are the elements of the array \(A\).
3. The third line contains an integer \(T\) representing the target sum.

outputFormat

Output to standard output (stdout) a single line: print "True" if there exists a subset whose sum equals \(T\); otherwise, print "False" (case-sensitive).

5
3 34 4 12 5
9

True