n和m，并返回用m个正整数相加得到n的可能方式数量。例如，像这样调用方法 partition(6, 2) 应该返回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
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...
递归多次后，当 m = 2 时，解为：
first part = 1 => second part = n - 1
first part = 2 => second part = n - 2
first part = 3 => second part = n - 3
etc...
因此，当 m = 2 时的解数等于第一部分选项的数量。
要仅计算唯一解并丢弃重复，使得 2+4 和 4+2 不会同时被计数，只考虑部分形成非降序列的解；例如：
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
在一个上升序列中，第一部分的值永远不能大于n / m。
为了保持上升序列，每次递归都必须将前一部分的值作为其部分的最小值；例如：
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
为避免需要在每次递归中传递最小值，每个递归n - k, m - 1, k都被替换成n - k - (m - 1) * (k - 1), m - 1, 1，其具有相同数量的解决方案。例如：
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
这不仅简化了代码，还有助于提高使用记忆化技术时的效率，因为像 2+2+3、3+3+4 和 5+5+6 这样的序列都被替换为它们的标准形式 1+1+2，并且更小的一组中间计算会经常重复。
使用递归算法进行分区时，许多计算会被重复多次。随着n和m的增加，递归次数迅速变得巨大。例如，要解决用例150, 23（下图所示）时，需要计算用例4, 2 23,703,672次。
然而，唯一的计算数量永远不能超过n * m。因此，通过将每个计算的结果缓存在一个n*m大小的数组中，最多只需要做n * m次计算；在计算一次用例后，算法可以使用存储的值。这极大地提高了算法的效率。例如，如果没有记忆化技术，则需要422,910,232次递归才能解决用例150, 23；使用记忆化技术，只需要15,163次递归。
下图显示了此用例的缓存读取和写入。灰色单元格未使用，白色单元格已写入但从未读取。总共有2042次写入和12697次读取。
您会注意到顶部左侧和底部右侧的三角形从未使用过；而且m的值越接近n，未使用的区域就越大。为避免这种空间浪费，可以将两个三角形之间的平行四边形倾斜45°，通过在n-m，m中存储n，m的值来实现。因此，缓存大小从(n-1) * (m-1)减小到(n-m) * (m-1)，而n，m <= 150的最坏情况不再是149 * 149 = 22201，而是75 * 74 = 5550，大小不到原来的25%。
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)这个版本缓存了中间结果，比基础算法要快得多。即使是 JavaScript 实现，在 n = 150 的最坏情况下也可以在不到一毫秒的时间内解决。
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(n = 1000时最坏情况为m = 81，解为4.01779428811641e+29，此结果也几乎瞬间返回。因为它超出了JavaScript的最大安全整数253-1，所以它当然不是一个精确的结果。)
这个示例代码3采用记忆化和较小缓存的偏斜缓存索引版本以降低内存需求。
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>"); // 1255f[n][m][k]为和为n，有m个非降正整数且最后一个为k的划分数，则可以轻松看出更新步骤为：f[n][m][k] → f[n+l][m+1][l] for every l≥ k
f[n][m]，表示与最后一个数是哪个数无关的所有分区数量，在最后只需对所有的k求和。复杂度将会是O(n^2 m)。public static long p(final long n, final long m) {
System.out.println("n=" + n + ", m=" + m);
return p(n, 1, m);
}
private static long p(final long n, final long digitFrom, final long m) {
final long digitTo = n - m + 1;
if (digitFrom > digitTo) return 0;
if (m == 1) return 1;
long sum = 0;
for (long firstDigit = digitFrom; firstDigit <= digitTo; firstDigit++)
sum += p(n - firstDigit, firstDigit, m - 1);
return sum;
}
示例调试：
n=6, m=3
1+1+4
1+2+3
2+2+2
从调试版本开始：
public static long p(final long n, final long m) {
System.out.println("n=" + n + ", m=" + m);
return p(n, 1, m, new Stack<String>());
}
private static long p(final long n, final long digitFrom, final long m, Stack<String> digitStack) {
final long digitTo = n - m + 1;
if (digitFrom > digitTo) return 0;
if (m == 1) {
digitStack.push(n + "");
printStack(digitStack);
digitStack.pop();
System.out.println();
return 1;
}
long sum = 0;
for (long firstDigit = digitFrom; firstDigit <= digitTo; firstDigit++) {
digitStack.push(firstDigit + "+");
sum += p(n - firstDigit, firstDigit, m - 1, digitStack);
digitStack.pop();
}
return sum;
}
你可以先准备好加数序列，然后逐对顺序处理它们，逐步获得笛卡尔积。
作为加数序列，你可以使用带有比较器的TreeMap<int[]>，比较两个排序数组的内容，以摆脱重复组合，例如4+2 和 2+4。如果要保留这些组合，则可以使用一个二维数组int[][]。这可以简化代码，但需要更多的计算时间。
如果n = 6，则加数序列如下：
1: [1][2][3][4][5][6]
2: [1][2][3][4][5]
3: [1][2][3][4]
4: [1][2][3]
5: [1][2]
6: [1]
reduce 方法通过 5 个阶段，依次获取 笛卡尔积：
1: [1][2][3][4][5][6]
2: [1][2][3][4][5]
---
sum1: [1,1][1,2][1,3]...[2,1][2,2][2,3]...
3: [1][2][3][4]
---
sum2: [1,1,1][1,2,1]...[2,1,1][2,2,1]...[3,1,1][3,2,1]...
4: [1][2][3]
---
sum3: [1,1,1,1]...[2,1,1,1]...[3,1,1,1]...
5: [1][2]
---
sum4: [1,1,1,1,1]...[2,1,1,1,1]...
6: [1]
---
total: [1,1,1,1,1,1]...
int n = 6, m = 2; // n - sum, m - number of summands
Set<int[]> partition = IntStream.range(0, n)
// prepare sets of arrays of summands
.mapToObj(i -> IntStream.rangeClosed(1, n - i)
.mapToObj(j -> new int[]{j})
// Stream<TreeSet<int[]>>
.collect(Collectors.toCollection(
// comparing the contents of two arrays
() -> new TreeSet<>(Arrays::compare))))
// sequential summation of pairs of sets
.reduce((set1, set2) -> set1.stream()
// combinations of inner arrays
.flatMap(arr1 -> {
// sum of the elements of the first array
int sum = Arrays.stream(arr1).sum();
// if the specified number is reached
if (sum == n) // and the number of summands is reached
if (arr1.length == m) // don't increase this combination
return Arrays.stream(new int[][]{arr1});
else return Stream.empty(); // drop this combination
// otherwise continue appending summands
return set2.stream() // drop the combinations that are greater
.filter(arr2 -> Arrays.stream(arr2).sum() + sum <= n)
.map(arr2 -> Stream.of(arr1, arr2)
.flatMapToInt(Arrays::stream)
.sorted().toArray()) // the sorted array
// drop too long combinations
.filter(arr2 -> arr2.length <= m);
}) // set of arrays of combinations
.collect(Collectors.toCollection( // two arrays that differ
// only in order are considered the same partition
() -> new TreeSet<>(Arrays::compare))))
// otherwise an empty set of arrays
.orElse(new TreeSet<>(Arrays::compare));
// output, the integer partition with restricted number of summands
partition.stream().map(Arrays::toString).forEach(System.out::println);
输出：
[1, 5]
[2, 4]
[3, 3]
另请参阅：高效构建总和为特定数字的排列
既然您已经知道要使用多少位数，我相信您可以做到这一点。
首先，您可以通过重复执行partition(n, 2)来做到这一点。如果您想要n=3，m=3，您只需执行partition(n, 2)，然后对于每个答案，您都要执行partition(k, 2)。
例如：
partition(6, 3):
partition(6, 2):
5 + 1，4 + 2，3 + 3，2 + 4，5 + 1
partition(5, 2):
4 + 1，3 + 2 ...
然后将它们全部加在一起：
(4+1) + 1，(3+2)+1，(2+3)+1，(1+4)+1，(3+1)+2...
并将它们按大小排序（最大的数字排在前面）。
4+1+1，4+1+1...
然后您可以删除所有重复项。
Partition（n，2）将以O（n）运行（因为您只需要循环到n并执行x +（n-x））。您将不得不这样做的次数是某种O（m）。由于您知道它们都是整数，因此可以在n中进行排序。因此，我认为这将在O（n*m）中运行，这并不好，但如果n或m相对较小，则可能可用于您。