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
This is based on challenge 574 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.
Please log in to submit your solution.
Difficulty 

Average test runtime  0.71 
Points (changes over time)  10 
Tried by  10 users 
Solved by  8 users 
#  Name  Runtime  Points worth 

1  贝尔恩德  0.14  20 
2  Pascal  0.15  19 
3  ,s/java/NaN/gi  0.16  17 
4  Irfan  0.41  7 
5  Mac  0.48  6 
6  Dark  0.53  5 
7  Connor  0.54  5 
8  Skøgland  3.27  1 