How To Find total ways to achieve given sum with n throws of dice having k faces?

Calculate total number of ways to achieve given sum with n throws of dice having k faces.

For example,

Input:
Number of throws n is 2
Number of faces k is 6 (i.e. each dice has values from 1 to 6)
Desired sum is 10
Output:
Total number of ways are 3.
The possible throws are
(6, 4), (4, 6), (5, 5)

The problem has an optimal substructure as the problem can be broken down into smaller subproblems which can further be broken down into yet smaller subproblems, and so on.
The idea is to use recursion to solve this problem. For each throw, we reduce the desired sum by values from 1 to k and recurse for remaining sum with throws left. If the desired sum is reached with n dices, we have found a way.

C implementation –

Output:

Total number of ways are 140

The time complexity of above solution is exponential and auxiliary space used by the program is O(1).

Above solution exhibits overlapping subproblems. If we draw the recursion tree of the solution, we can see that the same sub-problems are getting computed again and again. We know that problems having optimal substructure and overlapping subproblems can be solved by using dynamic programming, in which subproblem solutions are memoized rather than computed again and again. The Memoized version follows the top-down approach, since we first break the problem into subproblems and then calculate and store values. The approach is illustrated below in C –

Output:

Total number of ways are 140

The time complexity of above solution is O(n x k x sum) and auxiliary space used by the program is O(n x sum).

We can also solve this problem in bottom-up manner. In the bottom-up approach, we solve smaller sub-problems first, then solve larger sub-problems from them.