Edited in the light of Byron's correction to the original:
The answer is the coefficient of $u^x$ in the expansion of $$\sum_{y=0}^x(u^{a_1}+u^{a_2}+\cdots+u^{a_r})^y$$ which can be helpful if there is something special about $a_1,a_2,\dots,a_r$ enabling you to simplify this expression; otherwise, it's just a rewording of your problem. But this means your problem is no easier than that of finding a particular coefficient in this expansion, which suggests that most of the time there is no method significantly better than brute force; it's just a question of how cleverly you can arrange for the force to be applied.
As for making it "solvable in a few seconds," you may be asking for too much. Let's look in some detail at a very small example of what you want to do: how many ways to get 100 with 2s, 3s, and 5s?
Well, there's one way using just 5s. You could use 17 5s and 5 3s; there are 22-choose-5 ways to do that. Or you could use 14 5s and 10 3s; 24-choose-10 ways. Carrying on, we see that if you use just 3s and 5s, there are $$1+{22\choose5}+{24\choose10}+\cdots+{32\choose30}$$ ways. Now there's a similar formula for using just 2s and 5s, and another one for just 2s and 3s. Now what if we use 2s, 3s, and 5s? We could use 19 5s, a 3, and a 2; that gets you a multinomial coefficient, 21-choose-19,1,1. Then there's a 22-choose-18,2,2, and there's a 23-choose-17,3,3 and a 24-choose-17,1,6 and so on and so forth. A simple formula? Maybe, but I don't see it. Although I'd be interested to see what Henning's method does with this example.
There are many known formulas for the restricted integer composition problem. The one you have given,
$$p(n,m,k)=\sum_{i=0}^k p(n-i,m-1,k)$$
characterizes restricted integer compositions as extended binomial coefficients. If $k=1$, this is simply the formula for the binomial coefficients ($C(m,n)=C(m-1,n)+C(m-1,n-1)$). So, your problem can be seen as a natural generalization of binomial coefficients and your numbers generate a Pascal triangle like array.
This sequence may also be of relevance http://oeis.org/A008287
EDIT
To compute the number $p(n,m,k)$ based upon the above recurrence, set up a (sufficiently) large matrix $T(i,j)$, with all elements initialized to zero. Set $T(0,0)=1$. Then, for $i>0$, compute $T(i,j)=\sum_{i=0}^k T(i-1,j-i)$, until you arrive at your desired row $m$ and column $n$. This should be pretty fast, there is no need for exhaustive enumeration. For instance, a python script to compute $p(n,m,k)$ would be
n=8; m=6; k=9
T=[[0 for i in xrange(100)] for j in xrange(100)] # enough memory
T[0][0]=1
for j in xrange(1,m+1):
for i in xrange(n+1):
for r in xrange(k+1):
if i-r>=0: T[j][i]+=T[j-1][i-r]
print T[m][n]
Runtime is $O(mnk)$.
Best Answer
Assuming that the numbers are positive integers,
This is closely related to the Frobenius Coin Problem which says that there is a maximum number $\displaystyle F$ (called the Frobenius number) which is not representable. It is NP-Hard to find out the Frobenius number when there are at least $\displaystyle 3$ numbers.
For a formula like approach to determine if such a representation is possible or not, you can use generating functions, which can be used to give a pseudo polynomial time algorithm, polynomial in size $\displaystyle W = n_1 + n_2 + \cdots + n_k$.
If the numbers are $\displaystyle n_1, n_2, \dots, n_k$ and you need to see if they can be summed to $\displaystyle S$ then the number of ways it can be done is the coefficient of $\displaystyle x^S$ in
$$\displaystyle (1+x^{n_1} + x^{2n_1} + x^{3n_1} + \cdots )(1+ x^{n_2} + x^{2n_2} + x^{3n_2} + \cdots ) \cdots (1 + x^{n_k} + x^{2n_k} + x^{3n_k} + \cdots )$$
$$\displaystyle = \dfrac{1}{(1-x^{n_1})(1-x^{n_2}) \cdots (1-x^{n_k})}$$
Using partial fractions this can be written as
$$\displaystyle \sum_{j=1}^{m} \dfrac{C_j}{c_j - x}$$
where $\displaystyle C_j$ and $\displaystyle c_j$ are appropriate complex numbers and $\displaystyle m \le n_1 + n_2 + \cdots + n_k$.
The coefficient of $\displaystyle x^S$ is thus given by
$$\displaystyle \sum_{j=1}^{m} \dfrac{C_j}{c_j^{S+1}}$$
which you need to check is zero or not.
Of course, this might require quite precise floating point operations and does not actually tell you what numbers to choose.