Search code examples
javaalgorithmcomputation

All combinations of dividing an integer into several "groups"

Let's say I= have 5 sweets and I want to find all possible combinations of sharing them among my 3 kids.

This will be like something below:

5 for kid_A, 0 for kid_B, 0 for kid_3
0 for kid_A, 5 for kid_B, 0 for kid_3
....
4 for kid_A, 1 for kid_B, 0 for kid_3
4 for kid_A, 0 for kid_B, 1 for kid_3
....
and so on

Is there an algorithm to find this combinations?

So far, I have managed to compute the first 3 combinations, where I give all my sweets to one of my kids, and the remaining get 0; but I'm lost on how to divide once I'm done with this first iteration.

Solution

  • There are three aspects to this problem:

    • How many ways can I give one child up to N sweets? (permutations per child)
    • For each of those, how many ways can I give another child the remaining N sweets? (recursion, maybe)
    • When do I stop dividing out sweets? (termination)

    How many ways you can give a child n sweets is simple: you get one permutation for each of 0 -> n, e.g. the first child can be given 0, 1, 2, 3, 4 or 5 sweets.

    For the second child, you can repeat this once you subtract the first child's number of sweets. So, for 0 -> m, where m = 5 - n.

    For each of these permutations of n and m, the third child simply gets the remainder: t = 5 - (n + m).

    From this, you can formulate two loops to generate your permutations. There is a more general case for any amount of children or sweets, but at you have to be careful around your recursing (stack size problems) and aware that for large numbers a number of combinations may be huge.