
本文详解如何用递归算法生成所有长度为 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 存在两个严重问题:① 允许0导致结果含零(违背“正整数”隐含前提);② 上界错误,易遗漏如[47,1,1,1]这类大数在前的组合。正确上界应为sum − n + 1(保证后续n−1个数最小总和为n−1)。
✅ 推荐 PHP 实现(含校验与注释):
function getCombinations(int $sum, int $n): array
{
// 边界检查:和必须 ≥ n(每个数至少为 1)
if ($sum <p>⚠️ 注意事项: </p>
-
性能提示:该算法时间复杂度为 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)的递归建模是解决此类问题的关键——明确子问题定义(固定长度、递减和)、设置合理枚举范围、并严谨处理边界条件,即可稳健生成全部有序正整数组合。










