I'm trying to solve pretty complex problem with combinatorics.
Namely, we have given three numbers N, K, M. Now we want to count how many different arrays of integers are there with length N, sum K and all the elements in the range [1, M]
Constraints:
- 1 <= N <= 100
- 1 <= K <= 100
- 1 <= M <= 100
Example
Let's say N = 2, K = 5, M = 3. This means that we want to count arrays of integers of size 2 with sum of all elements equal to 5 and elements in range [1, 3]. There are total of 2 arrays: {2, 3} and {3, 2}. Please note that the order of the elements also matters, {2, 3} is not equal to {3, 2}
Second example: N = 4, K = 7, M = 3. We want to count arrays of length 4, sum of 7 and elements in range [1, 3].
There are total of 16 possible way of arrays: (1,1,2,3), (1,1,3,2), (2,1,1,3), (3,1,1,2), (2,3,1,1), (3,2,1,1), (1,2,3,1), (1,3,2,1), (1,2,1,3), (1,3,1,2), (1,2,2,2), (2,1,2,2), (2,2,1,2), (2,2,2,1)
What I have tried
I know that one solution is to generate all possible arrays, but such algorithm in best case will work in complexity O(N!) which is far too big for N = 100. I started thinking about solving this with three-dimensional dynamical programming, but I cannot find the relations between the states.
I'm thinking about this way: Let f(i, j, l) be the number of arrays of length i, sum j, and largest element l. We can see that for i = 0 f(i,j,l) = 0, so this is I think the base case. Also f(1, 1, 1) = 1 is another base case.
Now I cannot find the relations between the states. Can you give me some hints how to find the relations between the states. Thanks in advance.