Make delicious recipes!

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:

Facebook comments:

Site Owner: Sachin Goyal