algorithm - 生成数字的分区

Question

我需要一种算法来生成所有可能的正数分区，我想出了一个(作为答案发布)，但它是指数时间。

该算法应返回一个数字可以表示为小于或等于其自身的正数之和的所有可能方式。因此，例如对于数字 5，结果将是:

• 5
• 4+1
• 3+2
• 3+1+1
• 2+2+1
• 2+1+1+1
• 1+1+1+1+1

所以我的问题是:是否有更高效的算法？

编辑:问题的标题是“数字的总和分解”，因为我真的不知道这叫什么。 ShreevatsaR pointed out它们被称为“分区”，因此我相应地编辑了问题标题。

Answer 1

它叫做 Partitions . [另见维基百科:Partition (number theory) .]

分区数 p(n) 呈指数级增长，因此您为生成所有 分区所做的任何操作都必然需要指数时间。

也就是说，您可以比您的代码做得更好。参见 this ，或其在 Python Algorithms and Data Structures 中的更新版本通过 David Eppstein .