Numbers. People generally dislike numbers, but let's ignore that for the time being and instead pretend that numbers are universally loved. Everyone carries heaps of numbers around with them, and you choose to capitalize on that fact. You offer the following (paid) service: given the list of numbers they carry around with them as well as their favourite number (not necessarily in that list), you tell them how many ways there are to combine their numbers such that the sum equals their favourite number. For example, given the list [4, 3, 2, 2, 1, 1] and the favourite number 4, you find that there are four ways to produce that number:
Note that a number can be used within a sum as many times as it appears in the list, and that a single number counts as a sum.
The input will contain one or more test cases, one per line. Each test case contains \(1 \leq f \leq 1000\), the favourite number, followed by \(1 \leq n \leq 12\), the number of integers in the list, followed by \(n\) integers \(x_1, \ldots, x_n\) with \(1 \leq x_i \leq 100\). If \(n=0\), it signals the end of the input.
For each test case, output a separate line that specifies how many combinations of numbers are possible that sum up to \(f\).
4 6 4 3 2 2 1 1 5 3 2 1 1 400 12 50 50 50 50 50 50 25 25 25 25 25 25 0 0
4 0 2
Please log in to submit your solution.
|Average test runtime||0.71|
|Points (changes over time)||10|
|Tried by||10 users|
|Solved by||8 users|