Subset Sum Problem

You are given a list of integers and a target sum. Your task is to determine whether there is a subset of the list whose sum is exactly equal to the target.

Formally, given a list \(A = [a_1, a_2, \dots, a_n]\) and a target integer \(T\), determine if there exists a subset \(S \subseteq A\) such that:

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

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

inputFormat

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

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 representing the elements of the array. If \(n = 0\), this line will be empty.
3. The third line contains an integer \(T\), the target sum.

outputFormat

Output to standard output (stdout) a single line containing True if there exists a subset of the array that sums up to \(T\), and False otherwise.

6
3 34 4 12 5 2
9

True