递归求解双元素数组的目标和序列问题求助

解题思路 #

• 递归+回溯核心：每次从数组中选取一个元素，将其加入临时序列，同时用目标和减去该元素的值，递归处理剩余的目标和。当剩余目标和为0时，当前临时序列就是一个有效解；若剩余目标和小于0，直接终止当前分支。
• 全元素遍历：每次递归都循环遍历数组的所有元素，这样能生成不同顺序的序列（比如{2,2,6}和{2,6,2}这类顺序不同的解都会被覆盖）。
• 回溯还原：递归返回后，要把临时序列中最后加入的元素移除，保证后续能尝试其他元素组合。

完整代码（C++实现） #

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

void findSequences(int currentSum, int target, vector<int>& arr, vector<int>& temp, vector<vector<int>>& result) {
    // 找到有效序列，存入结果集
    if (currentSum == target) {
        result.push_back(temp);
        return;
    }
    // 当前和超过目标，终止分支
    if (currentSum > target) {
        return;
    }

    // 遍历数组每个元素，尝试加入序列
    for (int num : arr) {
        temp.push_back(num);
        findSequences(currentSum + num, target, arr, temp, result);
        // 回溯，移除最后添加的元素
        temp.pop_back();
    }
}

int main() {
    vector<int> v = {2, 6};
    int d = 10;
    vector<vector<int>> result;
    vector<int> temp;

    findSequences(0, d, v, temp, result);

    // 输出所有解
    cout << "所有解：" << endl;
    for (auto& seq : result) {
        cout << "{";
        for (size_t i = 0; i < seq.size(); ++i) {
            if (i != 0) cout << ",";
            cout << seq[i];
        }
        cout << "} ";
    }
    cout << endl;

    return 0;
}

代码说明 #

• 递归函数findSequences负责遍历所有可能的元素组合：
  • currentSum记录当前临时序列的元素和，初始值为0；
  • 每次循环将数组中的一个元素加入临时序列temp，递归处理更新后的currentSum；
  • 递归返回后弹出元素，实现回溯，确保能尝试其他组合；
• 主函数初始化数据、调用递归函数后，遍历结果集输出所有符合要求的序列。

内容的提问来源于stack exchange，提问作者Severjan Lici