Subset Sum Problem

Given an array of integers (which may include negative numbers) and a target sum \(T\), determine whether there exists a subset whose sum is exactly \(T\). Formally, you are given an integer \(N\) (the number of elements), an integer \(T\) (the target sum), and an array \(a\) of \(N\) integers. You need to decide if there exists a subset \(S \subseteq \{0, 1, \ldots, N-1\}\) such that \(\sum_{i \in S} a_i = T\).

The problem can be approached using dynamic programming by creating a state that tracks reachable sums by considering an offset for possible negative values. The offset is typically chosen to be sufficiently large so that all sums can be mapped to non-negative indices.

inputFormat

The first line contains two space-separated integers \(N\) and \(T\): the number of elements in the array and the target sum respectively.

The second line contains \(N\) space-separated integers representing the elements of the array.

outputFormat

Output a single line containing YES if there exists a subset of the array whose sum equals \(T\), otherwise output NO.

5 9
3 34 4 12 5

YES