Count the number of ways N dices can make sum S - PrismoSkills

Count the number of ways N dices can make sum S - PrismoSkills
Problem: Given N dices. Each dice has A faces.
Find the total number of ways these dices can make sum S when all are thrown together.
http://www.geeksforgeeks.org/dice-throw-problem/

Let the function to find X from n dice is: Sum(m, n, X)
The function can be represented as:
Sum(m, n, X) = Finding Sum (X - 1) from (n - 1) dice plus 1 from nth dice
               + Finding Sum (X - 2) from (n - 1) dice plus 2 from nth dice
               + Finding Sum (X - 3) from (n - 1) dice plus 3 from nth dice
                  ...................................................
                  ...................................................
                  ...................................................
              + Finding Sum (X - m) from (n - 1) dice plus m from nth dice

So we can recursively write Sum(m, n, x) as following
Sum(m, n, X) = Sum(m, n - 1, X - 1) + 
               Sum(m, n - 1, X - 2) +
               .................... + 
               Sum(m, n - 1, X - m)

Time Complexity: O(m * n * x) where m is number of faces, n is number of dice and x is given sum.

// The main function that returns number of ways to get sum 'x'

// with 'n' dice and 'm' with m faces.

int findWays(int m, int n, int x)

{

    // Create a table to store results of subproblems.  One extra

    // row and column are used for simpilicity (Number of dice

    // is directly used as row index and sum is directly used

    // as column index).  The entries in 0th row and 0th column

    // are never used.

    int table[n + 1][x + 1];

    memset(table, 0, sizeof(table)); // Initialize all entries as 0

 

    // Table entries for only one dice

    for (int j = 1; j <= m && j <= x; j++)

        table[1][j] = 1;

 

    // Fill rest of the entries in table using recursive relation

    // i: number of dice, j: sum

    for (int i = 2; i <= n; i++)

        for (int j = 1; j <= x; j++)

            for (int k = 1; k <= m && k < j; k++)

                table[i][j] += table[i-1][j-k];

 

    /* Uncomment these lines to see content of table

    for (int i = 0; i <= n; i++)

    {

      for (int j = 0; j <= x; j++)

        cout << table[i][j] << " ";

      cout << endl;

    } */

    return table[n][x];

}

Extreme case:

// When x is so high that sum can not go beyond x even when we

// get maximum value in every dice throw.

if (m*n <= x)

    return (m*n == x);

 

// When x is too low

if (n >= x)

    return (n == x);

Read full article from Count the number of ways N dices can make sum S - PrismoSkills