An apothecary stocks vials of several distinct integer strengths, with an unlimited supply of each strength. A dose is prepared by pouring some vials together; only the multiset of strengths used matters, not the order in which they are poured.
Count how many distinct multisets of vials have strengths summing exactly to the target dose T. The empty multiset sums to 0.
Line 1: two integers n and T.
Line 2: n space-separated distinct positive integers, the available vial strengths.
A single integer: the number of distinct multisets of vials summing to exactly T.
Example 1
Input
2 4 1 2
Expected
3
Explanation
Multisets of {1,2} summing to 4: (1,1,1,1), (1,1,2), and (2,2) -> 3.
Example 2
Input
2 0 3 7
Expected
1
Explanation
Only the empty multiset sums to 0, 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 →