A loading dock has n crates in a line; crate i has a positive integer weight. You may select any subset of the crates (possibly none) to load onto a cart. Determine whether some subset's weights sum to EXACTLY a target capacity T.
Line 1: two integers n T.
Line 2: n space-separated positive integers, the crate weights (empty if n = 0).
Print YES if some subset of the crates sums to exactly T, otherwise print NO. (The empty subset sums to 0, so if T = 0 the answer is always YES.)
Example 1
Input
4 10 2 3 5 9
Expected
YES
Explanation
Weights 2, 3 and 5 sum to exactly 10, so a valid subset exists: answer YES.
Example 2
Input
3 7 4 4 4
Expected
NO
Explanation
Any subset sums to 0, 4, 8 or 12 — never 7 — so the answer is NO.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →