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 –
 

Download   Run Code

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 –

 

Download   Run Code

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.

 
Exercise: Write bottom-up version of above solution.

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Shiva
Guest

Thanks for all these useful problems 🙂

Joey
Guest

In the example, some of the possible throws do not sum to 10 (ie. 6-1 and 1-6).