组合总和
力扣题目链接
题目描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
解题思路
回溯就按照递归的模板来写，确定好回溯路径和结束条件就行。
- 这里我们需要总和等于目标值，那么我们先对数组进行排序，从大到小，这样我们就可以从大的一端开始尝试着把数据放入，然后计算当前总和的值；
- 当值超过目标值时就往后取更小的数；
- 如果当前值等于目标值，把路径加入答案列表；
- 如果当前值小于目标值，就继续这个过程；
从大到小排序会让我们的数据选取更加具有目标性，可以减少很多不必要的路径试错。
题解
class Solution {
public:vector<vector<int>> ans;vector<int> path;void backTrack(vector<int>& candidates, int Index, int sum, int target){if(sum == target){ans.push_back(path);}else{for(int i = Index; i < candidates.size(); i++){if(candidates[i] + sum > target){continue;}sum += candidates[i];path.push_back(candidates[i]);backTrack(candidates, i, sum, target);sum -= candidates[i];path.pop_back();}}return;}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end(), greater<int>());backTrack(candidates, 0, 0, target);return ans;}
};
