Subsequence Sum Problem

Given an array of non-negative integers and a target integer \(k\), determine whether there exists a subsequence (i.e., a subset of the array, not necessarily contiguous) whose sum is exactly \(k\). Note that the empty subsequence (with sum zero) is considered valid.

Your task is to output "YES" if such a subsequence exists, otherwise output "NO".

Constraints:

• The first input line contains an integer \(n\) — the number of elements in the array.
• The second line contains \(n\) space-separated integers representing the array.
• The third line contains the target integer \(k\).

Hint: Use a dynamic programming approach with a boolean dp array of size \(k+1\) where \(dp[i]\) represents whether a subsequence summing to \(i\) is achievable.

inputFormat

The input format is as follows:

 n
 a1 a2 a3 ... an
 k

Where:

• \(n\) is the number of elements in the array.
• \(a1, a2, ..., an\) are the array elements.
• \(k\) is the target sum.

outputFormat

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

## sample

5
1 2 3 4 5
9

YES