如何生成整数分区？

Question

我有一个像1,2,3这样的数字列表,我想找到总结到特定数字的所有组合模式,例如5.例如:

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

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

你可以重复数字,只要他们没有超过你的金额.哪种方式最好编程呢？

Answer 1

这是对变更问题的略微修改.你应该能够找到关于这个问题的大量论文,动态编程解决方案不会超过20行代码.

http://en.wikipedia.org/wiki/Change-making_problem