Subset Sum Problem

You are given a list of n integers and a target value \(T\). Your task is to determine if there exists a subset of the given list whose sum is exactly equal to \(T\).

The input will be provided via standard input. The first line contains an integer denoting the number of elements \(n\). The second line contains \(n\) space-separated integers. The third line contains the target integer \(T\). Your output should be YES if there exists such a subset, and NO otherwise.

Note that the list can include negative numbers and zeros, and the solution may require checking all combinations. A set-based or dynamic programming approach can be used to efficiently solve the problem.

inputFormat

Input is read from stdin and consists of three parts:

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

outputFormat

Output to stdout. Print YES if there exists a subset of the list that sums to \(T\), and NO otherwise.

5
1 2 3 4 5
9

YES