An apothecary keeps n vials, each holding a whole number of millilitres. To fill a prescription you may pour out the full contents of any chosen subset of the vials (you never pour part of a vial). Selecting no vial at all yields a total of 0. Decide whether some subset of vials has contents that add up to exactly the required volume T.
Line 1: two integers n and T.
Line 2: n space-separated integers, the vial volumes.
Print YES if some subset of the vials sums to exactly T, otherwise NO.
Example 1
Input
4 7 2 3 5 8
Expected
YES
Explanation
The subset {2, 5} adds up to exactly 7, so the answer is YES.
Example 2
Input
3 10 2 4 5
Expected
NO
Explanation
The reachable subset totals are 0, 2, 4, 5, 6, 7, 9 and 11; none equal 10, 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 →