Subset Sum Problem

You are given an array of integers and a target sum k. Your task is to determine whether there exists a subset of the given array whose sum is exactly k. Note that by definition, the empty subset has a sum of 0, so if k = 0 the answer should be YES even if the array is non-empty.

A typical dynamic programming solution involves maintaining an array \(dp\) where \(dp[s]\) is true if a subset that sums to \(s\) can be formed from the elements seen so far. The recurrence is given in \(\LaTeX\) as follows:

\[ dp[s] = dp[s] \lor dp[s - \text{num}], \quad \text{for } s \geq \text{num} \]

Your solution must read input from standard input and write the result to standard output.

inputFormat

The first line contains two integers n and k, where n is the number of elements in the array and k is the target sum. The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output a single line: YES if there exists a subset whose sum is exactly k, and NO otherwise.

5 9
3 34 4 12 5

YES