Subset Sum Existence

You are given N integers and a target sum S. Your task is to determine whether there exists a subset of these integers that adds up exactly to S. Formally, let the integers be represented as a list values. You need to decide if there exists a subset V' ⊆ values such that

Note: The empty subset is considered to have a sum of 0. Thus, when S is 0, the answer is always "Yes".

This is a classical dynamic programming problem. The typical approach involves constructing a boolean array dp of size S+1 where dp[i] indicates if a subset with sum i can be formed from the given numbers.

inputFormat

The input is given via stdin and consists of two lines:

1. The first line contains two space-separated integers N and S, where N is the number of integers and S is the target sum.
2. The second line contains N space-separated integers representing the list values.

outputFormat

Output a single line to stdout containing either Yes if there exists a subset whose sum is equal to S, or No if there does not exist such a subset.

5 9
1 2 3 4 5

Yes