Harddp
Subset Sum
Time limit 2 s · Memory 64 MBAcceptance: —Solved by: 0
Statement
The first line contains n, the second line contains n positive integers, the third line contains S. Print YES if some subset of the numbers sums to exactly S, otherwise NO. The empty subset has sum 0.
Examples
Example 1
Input
5 1 2 3 4 5 11
Output
YES
Example 2
Input
3 2 4 6 5
Output
NO
Constraints
- 1 ≤ n ≤ 100
- 1 ≤ a_i ≤ 1000
- 0 ≤ S ≤ 10^5