Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Count the number of ways N dices can make sum S

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.

Solution: A recursive solution for this can be as follows:

```
public class SumFromDices
{

public static void main(String[] args)
{
int N = 5;
int diceValues[] = new int[N];
System.out.println ("Num solutions: "  + sFromN(N,6,20,diceValues) + ", callCount="+callCount);
}

static long callCount=0;
static int sFromN(int N, int A, int S, int []diceValues)
{
callCount++;

if (N<=0)
return 0;

if (N==1)
{
if (S>=1 && S<=A)
{
diceValues[0] = S;
for (int i : diceValues)
System.out.print(i+", ");
System.out.println();
return 1;
}
else
return 0;
}

int numSolutions = 0;
for(int i=1; i<=A; i++)
{
diceValues[N-1] = i;
numSolutions += sFromN(N-1, A, S-i, diceValues);
}

return numSolutions;
}
}

```

Order analysis: Order of execution for the above code is exponential.
It executes A loops in each recursive call and recursion depth is N.
So order is O(AN)

Example executions:

```
For N=3, A=4, S=8, number of ways are:

4, 3, 1,
3, 4, 1,
4, 2, 2,
3, 3, 2,
2, 4, 2,
4, 1, 3,
3, 2, 3,
2, 3, 3,
1, 4, 3,
3, 1, 4,
2, 2, 4,
1, 3, 4,

Num solutions: 12, callCount=21

```

Using dynamic programming by introducing a lookup:
```

public class SumFromDices {

public static void main(String[] args)
{
int N = 5;
int S = 20;
int diceValues[] = new int[N];
lookup = new int [N+1][S+1];
System.out.println ("Num solutions: "  + sFromN(N,6,S,diceValues) + ", callCount="+callCount);
}

static long callCount=0;
static int [][] lookup = null;

static int sFromN(int N, int A, int S, int []diceValues)
{
callCount++;

if (N<=0)
return 0;

if (N==1)
{
if (S>=1 && S<=A)
{
diceValues[0] = S;
for (int i : diceValues)
System.out.print(i+", ");
System.out.println();
return 1;
}
else
return 0;
}

if (lookup[N][S] != 0)
return lookup[N][S];

int numSolutions = 0;
for(int i=1; i<=A; i++)
{
diceValues[N-1] = i;
numSolutions += sFromN(N-1, A, S-i, diceValues);
}

lookup[N][S] = numSolutions;
return numSolutions;
}

}

```

The above lookup is not perfect however, since it only checks for non-zero lookup[N][S]
It can be improved by checking for zero lookup[N][S] values too.
For doing that, the lookup needs to be initialized to -1 too.

```
public class SumFromDices
{

public static void main(String[] args)
{
int N = 5;
int S = 20;
int diceValues[] = new int[N];
lookup = new int [N+1][S+1];
for (int i=0;i<=N;i++)
for (int j=0;j<=S;j++)
lookup[i][j] = -1;

System.out.println ("Num solutions: "  + sFromN(N,6,S,diceValues) + ", callCount="+callCount);
}

static long callCount=0;
static int [][] lookup = null;

static int sFromN(int N, int A, int S, int []diceValues)
{
callCount++;

if (N<=0)
return 0;

if (N==1)
{
if (S>=1 && S<=A)
{
diceValues[0] = S;
for (int i : diceValues)
System.out.print(i+", ");
System.out.println();
return 1;
}
else
return 0;
}

if (lookup[N][S] != -1)
return lookup[N][S];

int numSolutions = 0;
for(int i=1; i<=A; i++)
{
diceValues[N-1] = i;
numSolutions += sFromN(N-1, A, S-i, diceValues);
}

lookup[N][S] = numSolutions;
return numSolutions;
}
}

```

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: