Subset Sum Problem

Given a set of integers, determine whether there exists a subset whose sum is equal to a given target. This problem must handle negative numbers as well. Formally, given a set \(A = \{a_1, a_2, \dots, a_n\}\) and an integer \(T\), determine if there exists a subset \(S \subseteq A\) such that

\(\sum_{x \in S} x = T\)

If such a subset exists, output True; otherwise, output False.

inputFormat

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

• The first line contains an integer \(n\) representing the number of elements in the set.
• The second line contains \(n\) space-separated integers representing the elements of the set. If \(n = 0\), this line may be empty.
• The third line contains an integer \(T\) which is the target sum.

outputFormat

Output to STDOUT a single line: True if there exists a subset of the given integers with a sum exactly equal to \(T\), otherwise output False.

6
3 34 4 12 5 2
9

True