如何在递归回溯框架下实现目标和的唯一组合求解？

给定数字列表[2, 3, 5]与目标和8，需找出所有和为目标值的数字组合。现有一段未使用memoization的C++递归回溯代码，可生成所有可能组合，但会产生如[2,3,3]和[3,3,2]这类顺序不同的重复组合。询问：是否能在保持当前代码核心逻辑的前提下，实现求解所有唯一组合？

原代码如下：

#include<iostream>
#include<vector>

using namespace std;

bool bestSum( int targetSum, vector<int> &holder, vector<vector<int>> &combinations, 
vector<int> &path )
{
    if( targetSum == 0 )
    {
        combinations.push_back( path );
        return true;
    }
    if( targetSum < 0 )
    {
        return false;
    }

    bool possible = false;

    for( int i = 0; i < holder.size(); i++ )
    {
        int remainder = targetSum - holder[i];
        path.push_back(holder[i]);
    
        cout << "After pushing:";
        for( int j = 0; j < path.size(); j++ )
        {
            cout << path[j] << " ";
        }
        cout << endl;
    
        bool verdict = bestSum( remainder, holder, combinations, path );
        if( verdict == true )
        {
            possible = true;
        }
    
        path.pop_back();
        cout << "After popping:";
        for( int j = 0; j < path.size(); j++ )
        {
            cout << path[j] << " ";
        }
        cout << endl;
    
    }

    return possible;
}

int main()
{
    vector<int> holder = { 2, 3, 5 };
    int targetSum = 8;

    vector<vector<int>> combinations;
    vector<int> path;

    bool verdict = bestSum( targetSum, holder, combinations, path );

    for( int i = 0; i < combinations.size(); i++ )
    {
        for( int j = 0; j < combinations[i].size();j++)
        {
            cout << combinations[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

注：该代码无memoization时时间复杂度为指数级，添加后至多为低次多项式级。

解决方案 #

可以在保持原递归回溯核心逻辑的前提下实现唯一组合，核心思路是限制递归时的数字选择范围，只允许从当前索引及之后的数字中选取，避免生成顺序不同的重复排列。

修改要点 #

1. 给bestSum函数添加一个startIndex参数，用于控制当前递归层可选择的数字起始位置；
2. 将原代码中for循环的起始索引从0改为startIndex，确保下一层递归只能选择当前数字及之后的元素，不会回头选取前面的数字，从根源上避免重复组合。

修改后的完整代码 #

#include<iostream>
#include<vector>

using namespace std;

// 添加startIndex参数，控制当前层可选择的数字起始位置
bool bestSum( int targetSum, vector<int> &holder, vector<vector<int>> &combinations, 
vector<int> &path, int startIndex )
{
    if( targetSum == 0 )
    {
        combinations.push_back( path );
        return true;
    }
    if( targetSum < 0 )
    {
        return false;
    }

    bool possible = false;

    // 从startIndex开始遍历，而非从0开始
    for( int i = startIndex; i < holder.size(); i++ )
    {
        int remainder = targetSum - holder[i];
        path.push_back(holder[i]);
    
        cout << "After pushing:";
        for( int j = 0; j < path.size(); j++ )
        {
            cout << path[j] << " ";
        }
        cout << endl;
    
        // 递归调用时传递当前i作为下一层的startIndex
        bool verdict = bestSum( remainder, holder, combinations, path, i );
        if( verdict == true )
        {
            possible = true;
        }
    
        path.pop_back();
        cout << "After popping:";
        for( int j = 0; j < path.size(); j++ )
        {
            cout << path[j] << " ";
        }
        cout << endl;
    
    }

    return possible;
}

int main()
{
    vector<int> holder = { 2, 3, 5 };
    int targetSum = 8;

    vector<vector<int>> combinations;
    vector<int> path;

    // 初始调用时startIndex传0
    bool verdict = bestSum( targetSum, holder, combinations, path, 0 );

    cout << "\n最终唯一组合：" << endl;
    for( int i = 0; i < combinations.size(); i++ )
    {
        for( int j = 0; j < combinations[i].size();j++)
        {
            cout << combinations[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

效果说明 #

修改后代码会生成以下唯一组合：

2 2 2 2 
2 3 3 
3 5 

不会再出现[3,3,2]或[5,3]这类与已有组合顺序不同的重复项，完全符合需求。

内容的提问来源于stack exchange，提问作者Pratik Hadawale