193.回溯算法：组合总和（力扣）

本文主要是介绍193.回溯算法：组合总和（力扣），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码解决

class Solution {
public:vector<int> res; // 当前组合的临时存储vector<vector<int>> result; // 存储所有符合条件的组合// 回溯函数void backtrcing(vector<int>& nums, int target, int flag, int index) {// 如果当前组合的和超过了目标值，则返回if (flag > target) return;// 如果当前组合的和等于目标值，则将当前组合加入结果集if (flag == target) {result.push_back(res);return;}// 遍历候选数组for (int i = index; i < nums.size(); i++) {flag += nums[i]; // 将当前元素加入组合和res.push_back(nums[i]); // 将当前元素加入当前组合backtrcing(nums, target, flag, i); // 递归调用回溯函数，允许重复使用当前元素flag -= nums[i]; // 回溯，移除当前元素res.pop_back(); // 回溯，移除当前元素}}// 主函数vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtrcing(candidates, target, 0, 0); // 初始调用回溯函数return result; // 返回所有符合条件的组合}
};
测试用例

输入

vector<int> candidates = {2, 3, 6, 7}; int target = 7;

输出

[ [2, 2, 3], [7] ]

过程描述

初始状态：

candidates = {2, 3, 6, 7}
target = 7
res = []（当前组合为空）
result = []（所有符合条件的组合为空）

递归回溯：

从第一个元素 2 开始：
flag = 2，res = [2]，继续递归。
再次选择 2：
flag = 4，res = [2, 2]，继续递归。
再次选择 2：
flag = 6，res = [2, 2, 2]，继续递归。
再次选择 2：
flag = 8，超过目标值，回溯，移除最后一个 2。
尝试选择 3：
flag = 7，res = [2, 2, 3]，符合目标值，将组合加入 result，回溯，移除最后一个 3。
尝试选择 6 和 7：
超过目标值，回溯。
尝试选择 3：
flag = 5，res = [2, 3]，继续递归。
再次选择 3：
超过目标值，回溯。
尝试选择 6 和 7：
超过目标值，回溯。
尝试选择 3：
flag = 3，res = [3]，继续递归。
再次选择 3：
flag = 6，res = [3, 3]，继续递归。
尝试选择 3，6，7：
超过目标值，回溯。
尝试选择 6：
flag = 6，res = [6]，继续递归。
尝试选择 6，7：
超过目标值，回溯。
尝试选择 7：
flag = 7，res = [7]，符合目标值，将组合加入 result。

最终，result 包含所有符合条件的组合 [[2, 2, 3], [7]]。