回溯法求解求解子集合和问题递归

子集和问题是一个经典的组合优化问题，给定一个正整数集合S和一个目标数值T，求解S中所有元素的组合，使得这些元素的和等于T。回溯法是求解这个问题的一种常用方法。

具体来说，回溯法包括递归和回溯两个步骤。递归的过程中生成所有可能的组合，而回溯则是在每次递归中判断当前组合是否符合要求，并回溯到上一步状态以继续搜索。具体实现可以按照如下步骤进行：

1. 定义一个递归函数subsetSum，传入参数S、T、当前组合subset、组合元素的下标index和当前组合的和sum。

2. 在函数中先判断当前组合是否符合要求，如果符合，则输出该组合，否则继续递归。

3. 在递归过程中，首先判断是否已经搜索了全部元素，如果是，则返回。

4. 如果当前元素加入组合后不超过目标值T，则将该元素加入组合中，并递归调用subsetSum函数。

5. 如果当前元素加入组合后超过目标值T，则回溯到上一步状态，并继续搜索下一个元素。

具体实现代码如下：

void subsetSum(vector<int>& S, int T, vector<int>& subset, int index, int sum) {
    if (sum == T) {
        // 找到一个符合要求的子集
        for (int i = 0; i < subset.size(); i++) {
            cout << subset[i] << " ";
        }
        cout << endl;
        return;
    }
    if (index == S.size()) {
        // 已经搜索完所有元素
        return;
    }
    if (sum + S[index] <= T) {
        // 将当前元素加入组合
        subset.push_back(S[index]);
        subsetSum(S, T, subset, index + 1, sum + S[index]);
        // 回溯到上一步状态
        subset.pop_back();
    }
    // 继续搜索下一个元素
    subsetSum(S, T, subset, index + 1, sum);
}

调用方法如下：

vector<int> S = {1, 2, 3, 4, 5};
int T = 8;
vector<int> subset;
subsetSum(S, T, subset, 0, 0);

输出为：

3 5 
2 3 4 
2 6 
1 2 5 
1 3 4 

以上就是利用回溯法求解子集和问题的递归实现。