An expedition must load exactly k crates onto a sled. Each of the n available crates has a positive integer mass, and crates are distinct even when two share the same mass. The total loaded mass must equal exactly T.
Count how many ways there are to choose exactly k crates whose masses sum to T. Two choices differ if they use a different set of crate positions.
Line 1: three integers n, k, and T.
Line 2: n space-separated positive integers, the crate masses.
A single integer: the number of ways to choose exactly k crates summing to T.
Example 1
Input
4 2 7 1 3 4 6
Expected
2
Explanation
Pairs summing to 7 are {1,6} and {3,4}, so the answer is 2.
Example 2
Input
3 0 0 5 5 5
Expected
1
Explanation
Choosing 0 crates gives a total of 0, matching T, so there is exactly 1 way.
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 →