本文介绍如何用 php 递归生成指定和与长度的所有正整数有序组合（允许重复、顺序敏感），涵盖核心算法原理、可运行代码、边界处理及去重策略。
本文介绍如何用 php 递归生成指定和与长度的所有正整数有序组合（允许重复、顺序敏感），涵盖核心算法原理、可运行代码、边界处理及去重策略。
在组合数学中，将一个正整数 sum 拆分为 n 个正整数之和（顺序不同视为不同组合，即“有序组合”或“带序划分”），等价于求方程
$$ x_1 + x_2 + \cdots + x_n = \text{sum},\quad x_i \in \mathbb{Z}^+ $$
的所有解。注意：本问题默认要求每个数 ≥ 1（即正整数），但示例中出现了 [1, 1, 1, 47] 等含 1 的组合，且原始 JS 示例从 i = 0 开始循环——这实际隐含了非负整数（≥ 0）的设定。为与示例输出一致（如 [1,49], [1,1,1,47]），我们明确采用 正整数拆分（xᵢ ≥ 1），并据此修正算法逻辑。
✅ 正确递归思路（正整数约束）
若要求所有 xᵢ ≥ 1，则可通过变量替换简化：令 yᵢ = xᵢ − 1，则 yᵢ ≥ 0，且
$$ (y_1+1) + (y_2+1) + \cdots + (y_n+1) = \text{sum} \Rightarrow y_1 + \cdots + y_n = \text{sum} - n $$
此时问题转为求 sum − n 的 n 元非负整数有序组合，更易递归枚举。
但为保持直观性与教学清晰，我们直接在递归中强制最小值为 1：
function getCombinations(int $sum, int $n): array
{
// 边界检查：和必须至少为 n（每个数 ≥ 1）
if ($sum < $n || $n <= 0) {
return [];
}
if ($n === 1) {
return [[$sum]]; // 唯一解
}
$result = [];
// 第一个数 x1 可取 1 到 sum - (n-1)（预留至少 n-1 给其余位置）
$maxFirst = $sum - ($n - 1);
for ($x1 = 1; $x1 <= $maxFirst; $x1++) {
$remaining = $sum - $x1;
$subCombinations = getCombinations($remaining, $n - 1);
foreach ($subCombinations as $tail) {
$result[] = array_merge([$x1], $tail);
}
}
return $result;
}✅ 调用示例：
print_r(getCombinations(5, 2)); // [[1,4],[2,3],[3,2],[4,1]] print_r(getCombinations(5, 3)); // [[1,1,3],[1,2,2],[1,3,1],[2,1,2],[2,2,1],[3,1,1]]
⚠️ 注意：此版本生成有序组合（compositions），
[1,4]与[4,1]视为不同解——这与问题中[1,49],[2,48]的递增首项序列一致（但完整解集应包含所有排列）。若需严格按首项递增、后续非递减（即“整数分拆” partitions），需额外排序约束，不属于本题原始需求。
? 迭代优化与内存友好版（适用于大数值）
递归深度过大可能导致栈溢出。以下为等效迭代实现（使用栈模拟）：
function getCombinationsIterative(int $sum, int $n): array
{
if ($sum < $n || $n <= 0) return [];
if ($n === 1) return [[$sum]];
$stack = [[$sum, $n, []]]; // [remainingSum, remainingLength, currentPath]
$result = [];
while (!empty($stack)) {
[$rem, $len, $path] = array_pop($stack);
if ($len === 1) {
$result[] = array_merge($path, [$rem]);
continue;
}
$minVal = 1;
$maxVal = $rem - ($len - 1); // 预留至少 len-1 个 1
for ($x = $maxVal; $x >= $minVal; $x--) { // 逆序入栈以保持结果自然顺序
$stack[] = [$rem - $x, $len - 1, array_merge($path, [$x])];
}
}
return $result;
}? 去重与规范输出（如需无序唯一分拆）
若目标是数学意义上的整数分拆（partitions）——即 {1,1,47} 与 {1,47,1} 视为同一集合，仅保留升序排列版本，则应在生成后统一排序并去重：
function getUniquePartitions(int $sum, int $n): array
{
$comps = getCombinations($sum, $n);
$seen = [];
$unique = [];
foreach ($comps as $combo) {
sort($combo); // 升序标准化
$key = implode(',', $combo);
if (!isset($seen[$key])) {
$seen[$key] = true;
$unique[] = $combo;
}
}
return $unique;
}✅ 总结
- 该问题本质是生成正整数有序组合（compositions），可用简洁递归高效解决；
- 关键在于正确设置循环上下界：首项
x₁ ∈ [1, sum − n + 1]，确保剩余n−1项至少各为1； - 原始答案中
i 的写法会导致漏解（如 <code>50→[49,1]不会被捕获），已修正； - 实际应用中需根据场景选择：是否允许
0、是否要求去重、是否需内存优化； - 时间复杂度为 $ O\left(\binom{\text{sum}-1}{n-1}\right) $，即组合数级别，对大
sum或n需谨慎评估性能。
