我需要一个算法来生成所有可能的正数分区,我想出了一个(作为答案发布),但它是指数时间.
该算法应该返回所有可能的方式,数字可以表示为小于或等于其自身的正数之和.例如,对于数字5,结果将是:
所以我的问题是:有更高效的算法吗？
编辑:问题的标题是"数字的总和分解",因为我真的不知道这叫什么.ShreevatsaR指出它们被称为"分区",所以我相应地编辑了问题标题.
我的朋友给了我这个问题他在接受采访时被问到他无法回答.经过几个小时的思考,我们无法提出解决方案.
考虑一下三号.我需要编写一个程序来计算不同的方式,你可以将数字写为小于数字的数字之和.
例如:
如果数字是2,它可以写成sum(1,1)
如果数字是3,它可以写成sum(1,1,1),sum(1,2),sum(2,1)
如果数字是4,它可以写成sum(1,1,1,1),sum(1,3),sum(3,1),sum(1,2,1),sum(2,1) ,1),总和(1,1,2),总和(2,2).7种不同的方式
如果数字是5,它可以写成sum(1,1,1,1,1),sum(1,1,1,2),sum(1,1,2,1),sum(1, 2,1,1),总和(2,1,1,1)等
如何编写程序来确定数字可以分解为较小数字的总和的方式
如果使用http://www.programminglogic.com/integer-partition-algorithm/中的算法将sum(1,2)和sum(2,1)视为等效,我能够找到解决问题的方法.
但问题是总和(1,2)和总和(2,1)是不同的.我根本看不到这样做的模式.
任何帮助,将不胜感激.我只是想知道解决方案.