如何将一个正整数分成若干个正整数的和？

整数分区问题一直都是组合数学中的热门问题。当面对这个问题时，人们会想到将原问题转化为一个基于其它整数的子问题。而这种做法称为递归，是整数分区问题得以解决的关键。 一、什么是整数分区？ 整数分区，简单来说就是用正整数的和来表示一个正整数的方法个数。 比如说，将4分解成整数和的方法共有5种。这5种分别是： 4=4； 4=3+1； 4=2+2； 4=2+1+1； 4=1+1+1+1。 二、整数分区的计算方法 （一）递归算法 思路如下： （1）将n分成至多m个正整数之和的数目记作p(n,m)； （2）用第一个数(最大数)的大小分类讨论： ①如果第1个数>= m, 那么所有方案中都不可能出现m这个数，所以与第一个数的大小无关，其个数数目即为p(n-m,m)； ②如果第1个数< m, 那么所有p(n,m)的方案中，第一个数一定是<=m的，需要枚举；枚举时第一个数i可以从1到m， cnt(n,m,i)表示第一个数为i的方案数目，此时方案总数即为 p(n,m) = sum(cnt(n,m,i)),i=1:m. 枚举的过程实际上是在消耗第一个数的大小分量； （3）由于第一个数比较特殊，上面的计算只计算了第一个数<=m的方案的贡献，没有考虑第一个数>m的方案的贡献，这些方案的个数是p(n-m,m-1)，即第一个数直接从第2，3......m+1个数中选择。 代码实现如下：