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

**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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <stdio.h> // Function to calculate total number of ways to achieve given // sum with n throws of dice having k faces int count(int n, int k, int sum) { // if desired sum is reached with n dices if (n == 0) return (sum == 0); // desired sum can't be reached with current configuration if (sum < 0 || k * n < sum || n > sum) return 0; int res = 0; // recuse for all possible solutions for (int i = 1; i <= k; i++) res += count(n - 1, k, sum - i); return res; } // main function int main(void) { int n = 4; // n throws int k = 6; // values 1 - 6 int sum = 15; // desired sum printf("Total number of ways are %d", count(n, k, sum)); return 0; } |

`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 *Memo*ized 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 –

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include <stdio.h> #define N 10 #define SUM 100 // create a lookup table to store solutions of subproblems // lookup[i][j] stores number of ways to achieve sum j // with j throws of given dice. int lookup[N][SUM]; // Function to calculate total number of ways to achieve given // sum with n throws of dice having k faces int count(int n, int k, int sum) { // if desired sum is reached with n dices if (n == 0) return (sum == 0); // desired sum can't be reached with current configuration if (sum < 0 || k * n < sum || n > sum) return 0; // if sub-problem is seen for the first time, solve it and // store its result in an array or map if (lookup[n][sum] == 0) { // recuse for all possible solutions for (int i = 1; i <= k; i++) lookup[n][sum] += count(n - 1, k, sum - i); } // return solution to current sub-problem return lookup[n][sum]; } // main function int main(void) { int n = 4; // n throws int k = 6; // values 1 - 6 int sum = 15; // desired sum printf("Total number of ways are %d", count(n, k, sum)); return 0; } |

`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

Thanks for all these useful problems 🙂

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

Thanks Joey. We have corrected the typo.