难度中等
给你一个 无重复元素 的整数数组 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 。
仅有这两种组合。示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]示例 3：
输入: candidates = [2], target = 1
输出: []提示：
1 <= candidates.length <= 302 <= candidates[i] <= 40candidates的所有元素 互不相同1 <= target <= 40
解题思路：回溯 + 剪枝
本题和77.组合 (opens new window)，216.组合总和III (opens new window)的区别是：本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。
本题搜索的过程抽象成树形结构如下：
注意图中叶子节点的返回条件，因为本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的限制，只要选取的元素总和超过target，就返回！
注意本题和77.组合 (opens new window)、216.组合总和III (opens new window)的一个区别是：本题元素为可重复选取的。
所以我们传的 index 不能是 i+1，而得是 i，因为下一层可以包含当前这个节点值，也就是可以重复！
以及上面的版本一的代码大家可以看到，对于sum已经大于target的情况，其实是依然进入了下一层递归，只是下一层递归结束判断的时候，会判断sum > target的话就返回。
其实如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。
那么可以在for循环的搜索范围上做做文章了。
对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。
如果不排序的话，我们直接返回，那么可能会遗漏一些组合，因为下一个值可能是大于的，但是后一个值可能是小于的，那么就漏了！所以必须要排序！
class Solution {
public:
void backtracking(vector<int>& candidates, int target, int index, int sum)
{
if(sum >= target)
{
// 若等于才进行尾插
if(sum == target)
vv.push_back(v);
return;
}
for(int i = index; i < candidates.size() && sum + candidates[i] <= target; ++i) // jian'zh
{
v.push_back(candidates[i]); // 处理
backtracking(candidates, target, i, sum + candidates[i]); // 递归，其中index不用i+1了，为了可以重复读取当前的数
v.pop_back(); // 回溯
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
int sum = 0;
sort(candidates.begin(), candidates.end()); // 需要先排序
backtracking(candidates, target, 0, sum);
return vv;
}
private:
vector<vector<int>> vv;
vector<int> v;
};