39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。7 也是一个候选， 7 = 7 。仅有这两种组合。
思路：本题使用回溯算法，首先定义全局变量result为结果集，path为需要保存的路径，即每一种组合，sum为路径和。
回溯函数参数为整数数组 candidates，目标值target以及起始搜索位置startIndex。
终止条件为当sum值等于target时，将path加入结果集，return。
单层搜索逻辑：for循环横向搜索，范围为从startIndex到candidates.size()，for循环内部，sum加上当前节点值，path加入当前节点，然后往深处递归，递归时，因为每一个元素可以无限次取，所以递归传入的起始搜索位置就是当前节点。然后回溯，sum减去当前节点值，path弹出当前节点值。
这里可以进行一下剪枝操作，先把candidates从小到大排序，然后递归搜索时，如果当前路径和sum大于目标值target，剩下横向搜索的其他路径也终止，具体体现在对横向搜索的范围，即i < candidates.size() && sum + candidates[i] <= target。
代码：
class Solution { //39. 组合总和
public:
vector> result;
vector path;
int sum = 0;
void backtracking(vector& candidates, int target, int startIndex) {
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; ++i) {
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, i);
sum -= candidates[i];
path.pop_back();
}
}
vector> combinationSum(vector& candidates, int target) {
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0);
return result;
}
};
参考资料：代码随想录
