Subset Sum Problem

Given an array of integers and a target sum, determine if there exists a subset of the array whose sum is exactly equal to the target. This is a classic Subset Sum problem that can be solved using dynamic programming. One common approach is to use a boolean DP array dp where dp[i] indicates whether a sum of i is achievable. The recurrence can be written in LaTeX as: $$dp[i] = dp[i] \lor dp[i-num]$$ for each number num in the array. The solution should print YES if such a subset exists, otherwise NO.

inputFormat

The input is provided via standard input (stdin) and is structured as follows:

• The first line contains an integer N representing the size of the array.
• The second line contains N space-separated integers representing the elements of the array.
• The third line contains a single integer representing the target sum.

For example:

5
1 2 3 4 5
9

outputFormat

The output should be printed to standard output (stdout) as a single line containing either YES if there exists a subset of the array that sums to the target or NO if there is no such subset.

5
1 2 3 4 5
9

YES