Printing all dice combinations for a target sum using dynamic programming

Question

I have a problem to solve where we have n number of dice, each with 6 faces. I need to print all possible combinations for which the sum of the face-up numbers equals target.
for example: if n=2, target=10, then I need to print (4,6), (6,4), (5,5)

I was able to get to solve this with the below code but I want a more optimized solution using dynamic programming. Also, I was not sure how to calculate the time complexity for the below code, please help me to find the time complexity (Big O notation) of the below code and also help me to optimize and reduce the time complexity of this code using dynamic programming and memoization

public class Test {
    public static void main(String[] args) {
        int numDie = 2;
        int target = 10;
        int sides = 6;
        printTargetSumCombination(numDie, target, sides, new ArrayList<>());
    }

    private static void printTargetSumCombination(int numDie, int target, int sides, List<Integer> chosen) {
        if (numDie == 0) {
            if(chosen.stream().mapToInt(Integer::intValue).sum()==target)
                System.out.println(chosen);
        } else {
            for (int i = 1; i <= sides; i++) {
                chosen.add(i);
                printTargetSumCombination(numDie - 1, target, sides, chosen);
                chosen.remove(chosen.size() - 1);
            }
        }
    }
}

Answer 1

Here is a DP implementation.

The idea is: to solve the problem with n dice and target t, you can:

• Take the first die and consider all its possible values
• For every value v, consider the subproblem consisting of n - 1 dice and target t - v
• Combine v with the solutions of the subproblem

When a problem (n, t) is solved, its solutions are stored in a map (memoization).

import java.util.*;

public class DiceSolver
{
    private int sides;
    private HashMap<String, List<int[]>> cache;

    public DiceSolver(int sides)
    {
        this.sides = sides;
        cache = new HashMap<String, List<int[]>>();
    }

    public List<int[]> getSolutions(int numDice, int target)
    {
        // No need to compute anything if the target is out of reach
        if(target < numDice || target > sides * numDice)
            return Collections.emptyList();

        String key = numDice + "|" + target;
        List<int[]> solutions = cache.get(key);
        if(solutions==null)
        {
            // Compute the solutions and store them in the cache
            solutions = computeSolutions(numDice, target);
            cache.put(key, solutions);
        }
        return solutions;
    }

    private List<int[]> computeSolutions(int numDice, int target)
    {
        if(numDice > 1)
        {
            List<int[]> solutions = new ArrayList<int[]>();
            for(int v=1;v<=sides;v++)
            {
                // Combine the first die with the solutions of the subproblem
                for(int[] sol : getSolutions(numDice - 1, target - v))
                    solutions.add(prepend(v, sol));
            }
            return solutions;
        }
        else
        {
            // 1-die problem
            return Collections.singletonList(new int[]{target});
        }
    }

    private static int[] prepend(int val, int[] arr)
    {
        int[] res = new int[arr.length + 1];
        res[0] = val;
        System.arraycopy(arr, 0, res, 1, arr.length);
        return res;
    }

    public static void main(String[] args) 
    {
        DiceSolver solver = new DiceSolver(6);
        List<int[]> solutions = solver.getSolutions(2, 10);
        solutions.forEach(sol -> System.out.println(Arrays.toString(sol)));
    }
}

Output:

[4, 6]
[5, 5]
[6, 4]