求助：如何用递归函数实现动态层数嵌套循环匹配指定和？

已通过固定3层的nested_loops实现了找出maxno范围内、长度为maxloop的递增整数组合，且组合和等于matchsum的功能，但该实现循环层数固定，无法动态扩展（比如改成10层）。尝试用recursive_loops实现递归版本，但输出结果与嵌套循环不符，请求修正。

驱动代码 #

#include <iostream>
#include <vector>

using namespace std;

void nested_loops(unsigned int loop, const unsigned int &maxloop, 
           unsigned int no, const unsigned int &maxno, 
           unsigned int sum, const unsigned int &matchsum,
           vector<unsigned int> &pos, vector<vector<unsigned int>> &positions);
           
void recursive_loops(unsigned int loop, const unsigned int &maxloop, 
           unsigned int no, const unsigned int &maxno, 
           unsigned int sum, const unsigned int &matchsum,
           vector<unsigned int> &pos, vector<vector<unsigned int>> &positions);
           
void show_positions(const vector<vector<unsigned int>> &positions);

int main()
{
    vector<vector<unsigned int>> positions;
    vector<unsigned int> pos;

    nested_loops(1, 3, 1, 20, 1, 15, pos, positions);
    cout << "\nPositions size after nested_loops:" << positions.size() << endl;
    show_positions(positions);
    
    
    positions.clear();
    pos.clear();
    
    recursive_loops(1, 3, 1, 20, 1, 15, pos, positions);
    cout << "\nPositions size after recursive_loops:" << positions.size() << endl;
    show_positions(positions);
    
    return 0;
}
 
void show_positions(const vector<vector<unsigned int>> &positions)
{
    vector<unsigned int> pos;
    for(int i=0; i<positions.size(); ++i)
    {
        cout << endl;
        pos = positions[i];
        for(int j=0; j<pos.size(); ++j)
        {
            cout << " " << pos[j];
        }
    }   
    cout << endl << endl;   
}

可正常运行的嵌套循环代码（nested_loops） #

void nested_loops(unsigned int loop, const unsigned int &maxloop, 
           unsigned int no, const unsigned int &maxno, 
           unsigned int sum, const unsigned int &matchsum,
           vector<unsigned int> &pos, vector<vector<unsigned int>> &positions)
{
    for(int i1=no; i1<maxno-2; ++i1)
    {
        
    for(int i2=i1+1; i2<maxno-1; ++i2)
    {
        
    for(int i3=i2+1; i3<maxno; ++i3)
    {
        sum=i1+i2+i3;
        
        if(sum==matchsum)
        {
            pos.clear();
            pos.push_back(i1);
            pos.push_back(i2);
            pos.push_back(i3);
            
            positions.push_back(pos);
            
            break;
            
        }
        
    } } }
    
}

存在问题的递归函数代码（recursive_loops） #

void recursive_loops(unsigned int loop, const unsigned int &maxloop, 
           unsigned int no, const unsigned int &maxno, 
           unsigned int sum, const unsigned int &matchsum,
           vector<unsigned int> &pos, vector<vector<unsigned int>> &positions)
{
    pos.push_back(no);
    
    if(loop == maxloop)
    {
        if(sum+no == matchsum)
        {
            positions.push_back(pos);
        }
        return;
    }
    else
    {
        recursive_loops(loop+1, maxloop, no+1, maxno, sum+no+1, matchsum, pos, positions);
    
        if(no < maxno)
        {
            if(sum+no < matchsum)  
            {
                pos.pop_back();
                
                for(int i=no; no+i<maxno && sum+no+i<=matchsum; ++i)
                {
                    recursive_loops(loop+1, maxloop, no+i, maxno, sum+no+i, matchsum, pos, positions);
                    pos.pop_back();
                }
            }
        }
    }
    
    //pos.pop_back();
}

输出差异 #

• 预期：两个函数输出一致，得到12组符合条件的递增整数组合
• 实际：

Positions size after nested_loops:12

 1 2 12
 1 3 11
 1 4 10
 1 5 9
 1 6 8
 2 3 10
 2 4 9
 2 5 8
 2 6 7
 3 4 8
 3 5 7
 4 5 6


Positions size after recursive_loops:3

 1 2 6
 1 2 6
 1 4 5

原递归函数的问题在于：参数传递逻辑错误、递归分支混乱、pos的回溯时机不对，且没有正确模拟嵌套循环中“下一层循环起始值为当前值+1”的核心逻辑。以下是修正后的代码：

void recursive_loops(unsigned int loop, const unsigned int &maxloop, 
           unsigned int start, const unsigned int &maxno, 
           unsigned int current_sum, const unsigned int &matchsum,
           vector<unsigned int> &pos, vector<vector<unsigned int>> &positions)
{
    // 当前层数字上限：保证后续还有足够的数字可以选（每个都比当前大）
    unsigned int upper_limit = maxno - (maxloop - loop);
    for (unsigned int num = start; num <= upper_limit; ++num)
    {
        pos.push_back(num);
        unsigned int new_sum = current_sum + num;
        
        if (loop == maxloop)
        {
            // 选够指定层数，判断和是否符合要求
            if (new_sum == matchsum)
            {
                positions.push_back(pos);
            }
        }
        else
        {
            // 递归进入下一层，起始值为当前数字+1，保证组合递增
            recursive_loops(loop + 1, maxloop, num + 1, maxno, new_sum, matchsum, pos, positions);
        }
        
        // 回溯：移除当前选择的数字，尝试下一个可能值
        pos.pop_back();
    }
}

关键修正点 #

• 对齐嵌套循环逻辑：用for循环遍历当前层可选数字，下一层递归的起始值固定为num+1，严格保证组合的递增性。
• 边界优化：设置upper_limit确保后续还有足够的数字可以选择，和嵌套循环的maxno-2、maxno-1逻辑完全一致。
• 正确回溯：每次递归返回后弹出当前层选择的数字，保证pos的状态不会残留上一次的选择。
• 参数传递修正：直接传递累加后的new_sum，避免原代码中错误的求和逻辑。

注意事项 #

原驱动代码中调用nested_loops时传入的初始sum=1是多余的（函数内部直接重新计算了和），因此调用修正后的recursive_loops时，初始current_sum应传入0，即：

recursive_loops(1, 3, 1, 20, 0, 15, pos, positions);

修正后输出会与nested_loops完全一致，得到12组符合条件的递增整数组合。

内容的提问来源于stack exchange，提问作者musk's