组合总和习题分析

习题：（leetcode39）

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

分析：

回溯三部曲：

1.回溯函数模版返回值以及参数

2.回溯函数终止条件

3.回溯搜索的遍历过程

回溯伪代码:

void backtracking(参数){if(终止条件){存放结果;return;}
for(选择：本层集合中元素){处理节点;backtracking(路径，选择列表);//就是遍历下一层回溯，撤销处理结果;}
}

使用的方法是回溯，还是遍历整体得到答案，但此题不同，题目中说可以有重复的元素，此时就要考虑回溯函数中的参数如何写。可能大家也想到能不能通过创建used数组，来记录元素使用情况，如果在不满足target的情况下，让原元素仍可继续使用。但这种方法还是太麻烦。此题的巧妙之处就是在回溯函数中的参数如何满足题目条件。就是在定义的index在传递时传的是当前的遍历的值，即就是index=i传i的值。backtracking(candidates, target, sum, i);就是本题的关键，其余代码根据回溯三步曲和回溯模板就可以写出。

代码分析：

class Solution {
public:// 存储所有可能的组合结果vector<vector<int>> result;// 存储当前正在构建的组合vector<int> path;// 回溯函数，用于找到所有可能的组合void backtracking(vector<int>& candidates, int target, int sum, int index) {// 如果当前组合的和超过了目标值，则直接返回if (sum > target) return;// 如果当前组合的和等于目标值，则将当前组合添加到结果集中if (sum == target) {result.push_back(path);return;}// 遍历候选数字，从index开始，允许重复使用数字for (int i = index; i < candidates.size(); i++) {// 将当前候选数字加入当前组合，并更新当前组合的和sum += candidates[i];path.push_back(candidates[i]);// 递归调用回溯函数，由于可以重复使用数字，所以index仍然是ibacktracking(candidates, target, sum, i);// 回溯，移除最后加入的数字，并恢复之前的和sum -= candidates[i];path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtracking(candidates, target, 0, 0);return result;}
};