我要创建一个方法，它采用两个整数，让他们成为 N 和 M ，并返回如何许多方面有总结 M 正数来获得 N 。 例如，一个方法调用像这样分区（6,2）应该返回3，因为有3种方式可能。他们是 5 + 1 ， 4 + 2 和 3 + 3 。顺便说一句， 4 + 2 是一样的 2 + 4 ，因此该方法不应该指望他们为两个不同的变化。 是否有人知道一个解决问题的办法？

更新： N 和 M 不大于150

递归算法

要找到 N 与 M 部分的整数的所有分区，递归算法是显而易见的选择。对于这样 N，M ，通过每一个选项的算法运行 K = 1，2，3 ... 有关第一部分，并为每个选项是递归的情况下 N - K，M - 1 。例如：

  N = 16，M = 4
第一部分= 1 =＆GT;递归其中n = 15，M = 3
第一部分= 2 =＆GT;递归其中n = 14，M = 3
第一部分= 3 =＆GT;递归其中n = 13，M = 3
等等...
 

若干递归后，一点时 M = 2 ;那么解决方案是：

 第一部分= 1 =＆GT;第二部分= N  -  1
第一部分= 2 =＆GT;第二部分= N  -  2
第一部分= 3 =＆GT;第二部分= N  -  3
等等...
 

所以解决方案的数量 M = 2 等于在第一部分的选项的数量。

上升序列

要找出只有独特的解决方案，并丢弃重复，使 2 + 4 和 4 + 2 不同时算，只考虑解决方案，其中部分可以形成一个非递减序列;例如：

  N = 9，M = 3
分区：1 + 1 + 7 1 + 2 + 6 1 + 3 + 5 + 4 + 4
            2 + 2 + 5 2 + 3 + 4
            3 + 3 + 3
 

在一个上升的顺序，第一部分的值不能大于 N / M 。

递归与1

要维持一个上升顺序，每递归必须使用previous部分作为其组成部分的最小值的值;例如：

  N = 9，M = 3
K = 1 =＆GT; = 1 =＆gt;在N = 8，M = 2中，k＆GT递归; 1 + 7 2 + 6 3 + 5 + 4 4
K = 2 = GT; = 2 =＆gt;在N = 7，M = 2中，k＆GT递归; 2 + 5 + 3 4
K = 3 =＆GT; = 3 =＆gt;在N = 6，M = 2中，k＆GT递归; 3 + 3
 

要避免通过最小值与每一个递归，每次递归 N - K，M - 1，K 被替换 N - 的k - （米 - 1）*（K - 1）中，m - 1，1 ，它具有溶液的相同数目。例如：

  N = 9，M = 3
K = 1 =＆GT; = 1 =＆gt;在N = 8，M = 2中，k＆GT递归; 1 + 7 2 + 6 3 + 5 + 4 4
K = 2 = GT; = 1 =＆gt;在N = 5，M = 2中，k＆GT递归; 1 + 4 + 2 3
K = 3 =＆GT; = 1 =＆gt;在n = 2的M = 2中，k＆GT递归; 1 + 1
 

这不仅简化了code，还可以帮助使用记忆化时可提高效率，因为像 2 + 2 + 3 ， 3 + 3 + 4 和 5 + 5 + 6 都换成自己的规范形式 1 + 1 + 2 ，系统和一组中间计算的更小的重复更频繁。

记忆化

在用递归算法分割，许多计算都重复过无数次。而与n和m增加值，递归的数量迅速变得庞大;例如解决的情况下 150，23 （如下图所示），情况 4，2 计算23703672次。

然而，独特的计算数量不能大于 N * M 。因此，通过缓存每个计算的结果在N * M大小的数组，不超过 N * M以上计算以往任何时候都需要进行;具有计算的情况下，一旦后，该算法可使用的存储值。这巨大的提高了算法的效率;例如无记忆化，需要422910232递归破案 150，23 ;与记忆化，只需要15163递归。

下图显示的缓存读取和这种情况下写的。灰色细胞是未使用的，白色的单元编写的，但从来没有读过。有总共2042的写入和读出12697。

减小缓存大小

您会发现，在三角形的左上方和右下方是从未使用过;并且m越接近价值是n，则更大的未使用的区域越大。为了避免这种浪费的空间，parallellogram插图中的两个三角形可以通过45°扭曲，通过存储的值 N，M N - M，M 。缓存大小从而从减少（N - 1）*（M - 1）到（N - M）*（M - 1），最坏情况下 N，M＆LT; = 150 不再是149 *超过149 = 22201，而75 * 74 = 5550，少25％的大小。

code例1：不记忆化

code例2：快速版本，记忆化

这个版本，缓存中间结果，是比基本算法快得多。即使是这样的JavaScript实现解决了最坏的情况对于n = 150，在不到一毫秒。

（最坏的情况下，对于n = 1000，这是M = 81，解决了以4.01779428811641e + 29，而这个结果也返回因为JavaScript的浮点precision近瞬间，这当然不是一个确切的结果。）

code例子3：快速版本，记忆化和较小的缓存

这个版本使用了倾斜缓存索引来减少内存需求。

I have to create a method that takes two integers, let them be n and m, and returns how many ways there are to sum m positive numbers to get n. For example, a method call like this partition(6, 2) should return 3 because there are 3 ways possible. They are 5 + 1, 4 + 2, and 3 + 3. By the way, 4 + 2 is the same as 2 + 4, so the method should not count them as two distinct variations. Does anybody know a solution to the problem?

Updated: n and m are not greater than 150.

recursive algorithm

To find all partitions of an integer n with m parts, a recursive algorithm is the obvious choice. For the case n, m, the algorithm runs through every option k = 1, 2, 3... for the first part, and for each of these options it recurses with the case n - k, m - 1. For example:

n = 16, m = 4  
first part = 1  =>  recurse with n = 15, m = 3  
first part = 2  =>  recurse with n = 14, m = 3  
first part = 3  =>  recurse with n = 13, m = 3  
etc...

After a number of recursions, the point is reached where m = 2; then the solutions are:

first part = 1  =>  second part = n - 1  
first part = 2  =>  second part = n - 2
first part = 3  =>  second part = n - 3
etc...

So the number of solutions for m = 2 equals the number of options for the first part.

rising sequence

To find only unique solutions and discard duplicates, so that 2+4 and 4+2 are not both counted, only consider solutions where the parts form a non-decreasing sequence; for example:

n = 9, m = 3  
partitions: 1+1+7   1+2+6   1+3+5   1+4+4  
            2+2+5   2+3+4  
            3+3+3  

In a rising sequence, the value of the first part can never be greater than n / m.

recursion with minimum value of 1

To maintain a rising sequence, every recursion must use the value of the previous part as the minimum value for its parts; for example:

n = 9, m = 3  
k = 1  =>  recurse with n = 8, m = 2, k >= 1  =>  1+7  2+6  3+5  4+4  
k = 2  =>  recurse with n = 7, m = 2, k >= 2  =>  2+5  3+4  
k = 3  =>  recurse with n = 6, m = 2, k >= 3  =>  3+3

To avoid having to pass the minimum value with every recursion, every recursion n - k, m - 1, k is replaced with n - k - (m - 1) * (k - 1), m - 1, 1, which has the same number of solutions. For example:

n = 9, m = 3  
k = 1  =>  recurse with n = 8, m = 2, k >= 1  =>  1+7  2+6  3+5  4+4    
k = 2  =>  recurse with n = 5, m = 2, k >= 1  =>  1+4  2+3
k = 3  =>  recurse with n = 2, m = 2, k >= 1  =>  1+1

Not only does this simplify the code, it also helps improve efficiency when using memoization, because sequences like 2+2+3, 3+3+4 and 5+5+6 are all replaced by their canonical form 1+1+2, and a smaller set of intermediate calculations are repeated more often.

memoization

When partitioning with a recursive algorithm, many calculations are repeated numerous times. And with increasing values for n and m, the number of recursions quickly becomes huge; e.g. to solve case 150, 23 (illustrated below), case 4, 2 is calculated 23,703,672 times.

However, the number of unique calculations can never be greater than n * m. So by caching the result of each calculation in an n*m-sized array, no more than n * m calculation ever need be done; after having calculated a case once, the algorithm can use the stored value. This hugely improves the algorithm's efficiency; e.g. without memoization, 422,910,232 recursions are needed to solve the case 150, 23; with memoization, only 15,163 recursions are needed.

The illustration below shows cache reads and writes for this case. The grey cells are unused, the white cells are written but never read. There are a total of 2042 writes and 12697 reads.

reducing cache size

You'll notice that the triangles at the top left and bottom right are never used; and the closer the value of m is to n, the bigger the unused zones become. To avoid this waste of space, the parallellogram inbetween those two triangles can be skewed by 45°, by storing the value for n, m in n - m, m. The cache size is thus reduced from (n - 1) * (m - 1) to (n - m) * (m - 1), and the worst case for n,m <= 150 is no longer 149 * 149 = 22201, but 75 * 74 = 5550, less than 25% the size.

code example 1: without memoization

function partition(n, m) {
    if (m < 2) return m;
    if (n < m) return 0;
    if (n <= m + 1) return 1;
    var max = Math.floor(n / m);
    if (m == 2) return max;
    var count = 0;
    for (; max--; n -= m) count += partition(n - 1, m - 1);
    return count;
}

document.write(partition(6, 1) + "<br>");    // 1
document.write(partition(6, 2) + "<br>");    // 3
document.write(partition(9, 3) + "<br>");    // 7
document.write(partition(16, 4) + "<br>");   // 34
document.write(partition(150, 75) + "<br>"); // 8,118,264
// document.write(partition(150, 23));       // 1,901,740,434 (maximum for 150, takes > 10s)

code example 2: fast version with memoization

This version, which caches intermediate results, is much faster than the basic algorithm. Even this javascript implementation solves the worst-case scenario for n=150 in less than a millisecond.

function partition(n, m) {
    if (m < 2) return m;
    if (n < m) return 0;
    var memo = [];
    for (var i = 0; i < n - 1; i++) memo[i] = [];
    return p(n, m);

    function p(n, m) {
        if (n <= m + 1) return 1;
        if (memo[n - 2][m - 2]) return memo[n - 2][m - 2];
        var max = Math.floor(n / m);
        if (m == 2) return max;
        var count = 0;
        for (; max--; n -= m) count += (memo[n - 3][m - 3] = p(n - 1, m - 1));
        return count;
    }
}

document.write(partition(150, 23) + "<br>");  // 1,901,740,434
// document.write(partition(1000, 81));       // 4.01779428811641e+29

(The worst case for n = 1000, which is m = 81, solves to 4.01779428811641e+29, and this result is also returned nearly instantly. Because of the floating-point precision of javascript, this is of course not an exact result.)

code example 3: fast version with memoization and smaller cache

This version uses the skewed cache indexes to reduces memory requirements.

function partition(n, m) {
    if (m < 2) return m;
    if (n < m) return 0;
    var memo = [];
    for (var i = 0; i <= n - m; i++) memo[i] = [];
    return p(n, m);

    function p(n, m) {
        if (n <= m + 1) return 1;
        if (memo[n - m][m - 2]) return memo[n - m][m - 2];
        var max = Math.floor(n / m);
        if (m == 2) return max;
        var count = 0;
        for (; max--; n -= m) count += (memo[n - m][m - 3] = p(n - 1, m - 1));
        return count;
    }
}

document.write(partition(150, 23) + "<br>");  // 1,901,740,434
document.write(partition(150, 75) + "<br>");  // 8,118,264
document.write(partition(150, 127) + "<br>"); // 1255