One easy approach would be to enumerate all vectors of length, in which the elements have a value of [0 ... K]. That's K to the Nth combinations. Then for every such vector check whether its element sum is N. Although that might work for small N and K, it is a rather time consuming approach.

For large N and K the following approach might be faster: Think of the sum N as collection of balls that we want to distribute into dim bins. Start by distributing them into the first bins, always spending as many balls as fits into the bin. For N = 5, K = 3 and dim = 4 that would deliver:

3 2 0 0

We call this kind of distribution a "left-most" distribution as all balls reside as far left as posible according to our rules.

Now try to move a single ball at the time. We always take the first ball from the left that we can pick and only carry it forward a minimal number of bins until we can drop it legally. In our example that would yield

2 3 0 0

There is one more rule to consider: As soon as we have dropped a ball, we must redistribute the balls to its left to form a left-most configuration. So our next step will take one ball out of the left bin in drop it into the third bin, after which we redistrubte the remaining four balls anew:

3 1 1 0

We simply continue with these rules until we are no longer able move a ball forward. The following code represents these rules. I have written it in simple C-like style, so you can adapt it to whatever programming language you like.

```
void Distribute (int* vec, int dim, int k, int n)
{
for (int idx = 0; idx < dim; ++idx)
{
vec[idx] = min (n, k);
n -= vec[idx];
}
assert (n == 0);
}
bool MoveUp (int* vec, int dim, int k)
{
int collected = 0;
for (int idx = 0; idx < dim; ++idx)
{
if (collected == 0)
collected = vec[idx];
else
{
if (vec[idx] < k)
{
vec[idx] += 1;
Distribute (vec, idx, k, collected-1);
return true;
}
else
{
collected += k;
}
}
}
assert (collected != 0);
return false;
}
void PrintVec (int* vec, int dim)
{
for (int idx = 0; idx < dim; ++idx)
printf ("%d", vec[idx]);
printf ("\n");
}
int main()
{
int vec[4];
memset (vec, 0, sizeof vec);
Distribute (vec, 4, 3, 5);
PrintVec (vec, 4);
while (MoveUp (vec, 4, 3))
PrintVec (vec, 4);
return 0;
}
```

I guess that demonstrates nicely that it can be done in a simple iterative way - as so many problems. The code is not as elegant as the recursive one, for sure. But that was not your question I guess.

Anyway, what did you try?

—SA