Dice combinations to a total

Question

Trying to find a nice algorithm for working out d4 dice combinations for a total. For example 3 dice with four sides, all the combinations to make 4 would give: 004 013 112 022

I will be using c# but python or pseudo would be great. Just need some help for the algorithm. Would always be a four sided die but total and number of dice would be parameters.

Any ideas would be great. Thank you.

Answer 1

Here's a tweak to trincot's answer that doesn't require the creation of intermediate lists, and which computes a minimum value for the current dice, resulting in less wasted calls (.Net Fiddle).

public static ArrayList combos(int nDice, int tot, int max)
{
    var res = new ArrayList();
    combos(res, "", nDice, tot, max);
    return res;
}

private static void combos(ArrayList res, String sol, int nDice, int tot, int max)
{
    if(tot == 0)
    {
        res.Add(sol);
        return;
    }
    
    for(int side = 1+(tot-1)/nDice; side <= Math.Min(tot, max); side++)
        combos(res, sol+side, nDice-1, tot-side, side);
}

Test:

public static void Main (string[] args) {
    int nDice = 3;
    int nFaces = 4;
    for(int tot=1; tot<=nDice*nFaces+1; tot++)
    {
        Console.WriteLine ("\nTot: " + tot);
        foreach (var combo in combos(nDice, tot, nFaces)) {
            Console.WriteLine (combo);
        }
    }
}

Output:

tot: 1
1

tot: 2
11
2

tot: 3
111
21
3

tot: 4
211
22
31
4

tot: 5
221
311
32
41

tot: 6
222
321
33
411
42

tot: 7
322
331
421
43

tot: 8
332
422
431
44

tot: 9
333
432
441

tot: 10
433
442

tot: 11
443

tot: 12
444

tot: 13