C++递归统计三数凑5组合时循环未完全迭代如何解决？

问题根因 #

• 你观察的没错，循环只执行了i=0的情况，核心原因是循环体内直接写了return语句，第一次迭代时就直接结束函数返回结果，后续i=1到i=5的逻辑完全没有执行。你当前得到输出3，就是因为递归三层每层都只走了i=0的分支，返回1 + 下一层结果，最终计算结果为1+1+1=3。
• 递归逻辑设计错误：统计组合数需要累加所有合法取值对应的子问题结果，而不是直接返回1 + 子问题结果。

修复方案 #

统计有序三元组数量（即(1,2,2)和(2,1,2)视为不同情况） #

对应隔板法公式的非负整数解数量，本题sum=5、n=3的计算结果为21，修复后代码如下：

#include<bits/stdc++.h>
using namespace std;

int count_sum_5(int sum, int n)
{   
    // 边界：只剩1个数字时，只有1种选法（选sum本身）
    if(n == 1) return 1;
    int res = 0;
    // 遍历当前位所有合法取值，累加子问题结果
    for(int i = 0; i <= sum ; i++){
        res += count_sum_5(sum - i, n - 1);
    }
    return res;
}

int main()
{
    int sum = 5;
    int count_ele = 3;
    cout << count_sum_5(sum, count_ele);
}

统计无序组合数量（即(1,2,2)和(2,1,2)视为同一种情况） #

需要增加参数限制后选的数字不小于前一个，避免重复计数，本题计算结果为5，修复后代码如下：

#include<bits/stdc++.h>
using namespace std;

// 增加min_val参数，要求当前选的数不小于min_val，保证非降序避免重复
int count_sum_5(int sum, int n, int min_val)
{   
    if(n == 1) return sum >= min_val ? 1 : 0;
    int res = 0;
    for(int i = min_val; i <= sum ; i++){
        res += count_sum_5(sum - i, n - 1, i);
    }
    return res;
}

int main()
{
    int sum = 5;
    int count_ele = 3;
    cout << count_sum_5(sum, count_ele, 0);
}

内容的提问来源于stack exchange，提问作者Hiếu Võ Trần Minh