题目描述：
给你一个 无重复元素 的整数数组 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 <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都 互不相同
1 <= target <= 500
方法1 回溯 c++代码：
class Solution {
public:
void dfs(vector<int> candidates, int n, int temp, int target, vector<int> &temp_res, vector<vector<int>> &res){
//当前回溯深度等于n（已经查找到数组最后一个数），结束
if(temp==n)return;
//如果已经凑得target（剩余要凑的target=0），记录当前解，返回上一级回溯
if(target == 0){
res.emplace_back(temp_res);
return;
}
//否则继续查找
dfs(candidates,n,temp+1,target,temp_res,res); //第一种方案：跳过candidates[temp], 直接考虑下一个数字
//第二种方案：选择candidates[temp]
if(target - candidates[temp] >= 0){ //若当前数字不够凑target，还要继续在后面的数字中回溯查找
temp_res.push_back(candidates[temp]); //当前解中先记录当前数字
dfs(candidates,n,temp,target-candidates[temp],temp_res,res); //选择temp并继续回溯，凑target-candidates[temp]，！！！！每个数字可以被无限制重复选取，因此搜索的下标仍为temp而不是temp+1
temp_res.pop_back(); //若向后回溯过程中凑成功得到了解，会把temp_res记录在res中，但若回溯中没有找到解说明当前candidates[temp]不能要，需要恢复temp_res，把candidates[temp] pop掉
}
}
//组合数很大的问题，搜索可行解：使用回溯法(深度优先搜索)
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
int n = candidates.size();
vector<int> temp_res; //记录每一次找到的解
vector<vector<int>> res; //记录所有的解
//从数组第0个元素开始回溯查找，每次找到的解保存在temp_res,所有的解保存在res
dfs(candidates,n,0,target,temp_res,res);
return res;
}
};
因为只是回溯，没有剪枝所，相当于暴力搜索，所以速度很慢。
方法2 回溯+剪枝 c++代码：
class Solution {
public:
void dfs(vector<int> candidates, int n, int temp, int target, vector<int> &temp_res, vector<vector<int>> &res){
if(temp==n)return;
if(target == 0){
res.emplace_back(temp_res);
return;
}
for(int i=temp;i<n;i++){
//不可能向后找到解，剪枝！
if(target-candidates[i] < 0)break;
//否则选择i 继续向后回溯
temp_res.push_back(candidates[i]);
dfs(candidates,n,i,target-candidates[i],temp_res,res);
//回溯后恢复
temp_res.pop_back();
}
}
//组合数很大的问题，搜索可行解：使用回溯法(深度优先搜索)
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
int n = candidates.size();
//为了方便剪枝，先对数组从小到大排序
sort(candidates.begin(),candidates.end());
vector<int> temp_res; //记录每一次找到的解
vector<vector<int>> res; //记录所有的解
dfs(candidates,n,0,target,temp_res,res);
return res;
}
};
对回溯进行剪枝：
在对数组中的数字进行判断是否可以作为解的其中一个加数时，若对数组提前从小到大排序，那么当target-candidates[i] < 0时：就可以判定这之后所有的数字都将大于要凑的target，即不可能有解，可以不再回溯直接退出搜索。这一节省不必要的回溯的操作叫“剪枝”。
总结：
回溯法：
使用场景：当问题的组合数较大，需要找到一个最优解或找到多个解时，使用回溯法。
实现方法：使用深度优先搜索DFS，具体的可以使用递归，也可以使用for循环迭代实现。
提高速度：剪枝，以避免无效搜索。具体使用两种函数——限界函数（得不到最优解），**约束函数（剪去不符合要求的子树）**进行剪枝。
注意：
！此题限定每个数字都可以被重复使用，所以若选择当前数字candidats[temp]，下一次dfs的参数仍为temp而不是temp+1