本文详解如何用递归算法生成所有长度为 n、元素均为正整数且和为 target 的组合，支持 php/js 实现，涵盖基础逻辑、去重策略及边界注意事项。
本文详解如何用递归算法生成所有长度为 n、元素均为正整数且和为 target 的组合，支持 php/js 实现，涵盖基础逻辑、去重策略及边界注意事项。
在组合数学中，该问题属于带限制的整数拆分（Integer Composition）：要求将一个正整数 sum 拆分为恰好 n 个正整数之和（顺序不同视为不同组合，即 composition 而非 partition），每个部分 ≥ 1。例如 sum = 5, n = 3 的合法组合包括 [1,1,3]、[1,2,2]、[1,3,1] 等——注意 [1,1,3] 与 [1,3,1] 被视为不同结果，这是组合（ordered）而非拆分（unordered）的核心特征。
以下是推荐的递归实现思路：
-
基准情形：当
n === 1时，唯一解为[sum]； -
递归步骤：对当前首位数字
i枚举所有可能取值（从1到sum − n + 1，确保剩余n−1个数至少各为1），再递归求解getCombinations(sum − i, n − 1)，并将i前置拼接至每个子结果； -
关键修正：原始答案中
for ($i = 0; $i 存在两个严重问题：① 允许 <code>0导致结果含零（违背“正整数”隐含前提）；② 上界错误，易遗漏如[47,1,1,1]这类大数在前的组合。正确上界应为sum − n + 1（保证后续n−1个数最小总和为n−1）。
✅ 推荐 PHP 实现（含校验与注释）：
function getCombinations(int $sum, int $n): array
{
// 边界检查：和必须 ≥ n（每个数至少为 1）
if ($sum < $n || $n < 1) {
return [];
}
if ($n === 1) {
return [[$sum]];
}
$result = [];
// i 从 1 开始，最大取 sum - n + 1（留足 n-1 个 1）
for ($i = 1; $i <= $sum - $n + 1; $i++) {
$subCombinations = getCombinations($sum - $i, $n - 1);
foreach ($subCombinations as $sub) {
array_unshift($sub, $i); // 前置 i，保持顺序
$result[] = $sub;
}
}
return $result;
}
// 示例调用
print_r(getCombinations(5, 3));
// 输出：[[1,1,3], [1,2,2], [1,3,1], [2,1,2], [2,2,1], [3,1,1]]⚠️ 注意事项：
-
性能提示：该算法时间复杂度为 O(S^{n−1})，
sum或n较大时（如sum > 50,n > 6）会产生海量结果，建议增加maxResults限制或改用迭代+剪枝； -
去重需求：若需忽略顺序（即等价于无序拆分），应在生成后对每个组合
sort()并用array_unique($result, SORT_REGULAR)去重，但会丢失原始排列信息； -
扩展性：如需限定数值范围（如每项 ∈ [1,10]），可在循环中加入
if ($i >= $min && $i 条件； -
内存优化：对超大规模场景，建议改用生成器（
yield）逐个产出结果，避免全量数组驻留内存。
总结：掌握整数合成（composition）的递归建模是解决此类问题的关键——明确子问题定义（固定长度、递减和）、设置合理枚举范围、并严谨处理边界条件，即可稳健生成全部有序正整数组合。
