How do I generate integer partitions?

Question

I have a list of numbers like 1,2,3 and I want to find all the combination patterns that sum up to a particular number like 5. For example:

Sum=5
Numbers:1,2,3
Patterns:

1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
2 3

You're allowed to repeat numbers as far as they don't go over your sum. Which way would be best to program this?

Answer 1

I would do it recursively starting with the highest numbers first. then, each time in start with the highest level and go in as many levels as numbers. As soon as the cumulative level exceeds your value, drop down to the next number. If still too large (or small), immediately return back one level and decrease THAT to the next number down, then to the next deeper level starting at the top again..

Answer 2

This is a slight modification of the change making problem. You should be able to find plenty of papers on this problem, and a dynamic programming solution would take no more than 20 lines of code.

http://en.wikipedia.org/wiki/Change-making%5Fproblem

Answer 3

This might also help: Dynamic Programming: Combination Sum Problem

Answer 4

These are called the partitions of a number , and your problem seems to impose the constraint of which numbers you're allowed to use in the partition.