如何实现返回vector<string>类型的目标和子集递归函数？

我来帮你修正递归函数并详细解释如何实现这个需求。首先先分析一下你提供的代码存在的几个问题：每次递归调用会覆盖结果集、没有处理“不选当前元素”的分支、子集拼接逻辑错误，这些都会导致无法正确生成所有符合要求的子集。

修正后的完整代码 #

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<string> targetsum(vector<int>& array, int idx, int target) {
    // 基准情况1：剩余目标为0，返回空字符串作为有效子集的起点
    if (target == 0) {
        return {""};
    }
    // 基准情况2：索引越界或剩余目标为负，返回空向量表示此路径无解
    if (idx >= array.size() || target < 0) {
        return {};
    }
    
    vector<string> myans;
    
    // 选择当前元素：如果当前元素可以加入到子集中
    if (target >= array[idx]) {
        vector<string> subans = targetsum(array, idx + 1, target - array[idx]);
        // 将当前元素拼接到每个子结果的末尾，保持元素顺序
        for (string& s : subans) {
            if (s.empty()) {
                myans.push_back(to_string(array[idx]));
            } else {
                myans.push_back(s + " " + to_string(array[idx]));
            }
        }
    }
    
    // 不选择当前元素：直接递归处理下一个索引，合并结果
    vector<string> skipans = targetsum(array, idx + 1, target);
    myans.insert(myans.end(), skipans.begin(), skipans.end());
    
    return myans;
}

// 格式化打印结果的辅助函数
void printResult(const vector<string>& result) {
    cout << "[";
    for (size_t i = 0; i < result.size(); ++i) {
        if (i > 0) {
            cout << " , ";
        }
        cout << result[i];
    }
    cout << " ]" << endl;
}

int main() {
    int n;
    cin >> n;
    vector<int> array(n);
    for (int i = 0; i < n; ++i) {
        cin >> array[i];
    }
    int target;
    cin >> target;
    
    vector<string> result = targetsum(array, 0, target);
    printResult(result);
    
    return 0;
}

核心实现思路 #

这个递归函数基于回溯思想，通过对每个元素做“选/不选”的决策来生成所有符合条件的子集，关键逻辑如下：

• 参数设计：array是输入数组，idx是当前遍历的起始索引（避免重复生成相同子集），target是剩余需要达成的目标和。
• 基准条件：
  • 当target == 0时，返回包含空字符串的向量，代表找到一个有效子集的“起点”，后续可以拼接元素形成完整子集。
  • 当索引越界或target < 0时，返回空向量，表示这条路径无法得到有效子集。
• 递归分支：
  1. 选择当前元素：如果当前元素的值不超过剩余目标，递归处理下一个索引并将目标值减去当前元素。递归返回后，把当前元素拼接到每个子结果的后面（保持元素在原数组中的顺序），加入结果集。
  2. 不选择当前元素：直接递归处理下一个索引，剩余目标值不变，将返回的结果合并到当前结果集中。
• 0的特殊处理：因为0的加入不会改变目标和，所以当遍历到0时，选择0的分支会递归寻找和为原目标的子集，从而生成包含0的有效子集（比如示例中的1 5 0）。

示例运行结果 #

输入：

5
1 3 5 7 0
6

输出：

[1 5 , 1 5 0 ]

内容的提问来源于stack exchange，提问作者lakshay malhotra