使用回溯求解子集和问题用C++实现代码【输入样例】 5 10 2 2 6 5 4 【输出样例】 2 2 6

以下是使用回溯求解子集和问题的C++代码：

#include <iostream>
#include <vector>

using namespace std;

vector<int> nums;
vector<int> path;
int target;
bool found = false;

void dfs(int cur_sum, int start) {
    if (cur_sum == target) { // 找到一组解
        found = true;
        for (int i = 0; i < path.size(); i++) {
            cout << path[i] << " ";
        }
        cout << endl;
        return;
    }
    if (cur_sum > target || start >= nums.size()) { // 已经不可能找到解
        return;
    }
    for (int i = start; i < nums.size(); i++) {
        path.push_back(nums[i]);
        dfs(cur_sum + nums[i], i + 1);
        path.pop_back();
        if (found) { // 找到一组解就立即返回
            return;
        }
    }
}

int main() {
    int n, sum;
    cin >> n >> sum;
    nums.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    target = sum;
    dfs(0, 0);
    return 0;
}

输入样例：

5 10
2 2 6 5 4

输出样例：

2 2 6