Algorithm to split integer into groups of defined smaller integers

Question

I want to write a function that when given an integer, can partition it into groups of specified smaller integers.

Specifically, the passed in value needs to be split into a set of values of where those values can only be either 1, 5, or 10.

Additionally there is a condition that it must be split into at least 3 values in the set, but must also be the minimum amount of values in the set.

To give an example.

If 10 was passed in, it should output 5, 1, 1, 1, 1, 1

If 6 was passed in, it should output 1, 1, 1, 1, 1, 1,

If 15 was passed in, it should output 10, 1, 1, 1, 1, 1

If 16 was passed in, it should output 10, 5, 1

If 2 was passed in, it should output 1, 1

If 27 was passed in, it should output 10, 10, 5, 1, 1

I know this will probably involve using modulo and will probably be a multi-part algorithm. Just not sure how to approach the problem.

There are a lot of partition questions already but I've not seen any that are similar enough to help so any help is appreciated.

Answer 1

To put it in a slightly different way:

• compute a base solution: how many 10s as possible, then how many 5s as possible, then how many 1s as needed
• if you have 3 or more values you're done; otherwise
• if you have less than 3 values and there's at least one 10, split one 10 in two 5s
• if you still have less than 3 values and there's at least one 5, split one 5 in five 1s
• if you still have less than 3 values then the input was less than 3, so return the 1s you have or raise an error