Would you consider 2 + 2 + 1, and 1 + 2 + 2 as different sequences for N = 5, k = 3 ?

I believe you are asking for the number of partitions of a number into k parts.

Let us denote this number by f(n, k).

Now, there are two possibilities — Either there is some box which has exactly one candy or every box has more than one candy.

If the smallest number of candies in any box is 1. Then the problem reduces to finding f(n — 1, k — 1).

Otherwise, let every box have at least one candy. Then we place one candy in each of the k boxes, and now distribute the remaining (n — k) candies into k boxes. This is given by f(n — k, k)

f(n, k) = f(n — 1, k — 1) + f(n — k, k)

I hope this helps.

f(0, k) = 0, for all k f(1, 1) = 1 f(n, 1) = f(n, n) = 1, for all n

You want all boxes to have at least 1 candy. Then you can remove this restriction by simply subtracting K from N. Now the problem is simply to find the number of combinations with repeatings. This count is equal to C(n + k - 1, k - 1), where C(n, k) is the number of ways to chose k out of n values. You can find an easy explanation by googling "combinations with repeatings", or I can explain it if you want (googling will be faster).

This problem if I'm not mistaken was asked in Codechef long challenge in the beginning of 2017.