A keyring holds n fobs, each with a whole-number weight. You want to detach a subset of fobs whose weights add up to exactly T, using as few fobs as possible. Each fob may be used at most once. Report the minimum number of fobs needed to reach exactly T, or -1 if no subset of fobs sums to T. Reaching T = 0 needs zero fobs.
Line 1: two integers n and T.
Line 2: n space-separated integers, the fob weights.
A single integer: the minimum number of fobs summing to exactly T, or -1 if impossible.
Example 1
Input
5 10 1 2 3 8 5
Expected
2
Explanation
The two fobs {2, 8} sum to exactly 10; no single fob equals 10, so the minimum is 2.
Example 2
Input
3 7 2 4 6
Expected
-1
Explanation
The reachable subset totals are 0, 2, 4, 6, 8, 10 and 12; 7 is not among them, so the answer is -1.
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 →