题目链接

中文

https://leetcode-cn.com/problems/combination-sum/description/

英文

https://leetcode.com/problems/combination-sum/description/

解题思路

1.首先对candidates进行排序，这样可以在循环遍历时先取到小的加数，保证加数有效性，并且可以在加数较大时直接退出循环，避免不必要的循环。排序后进入递归函数。

递归方法

1.在递归函数中循环遍历candidates数组,将target和candidates[i]中的每个数字进行比较，若candidates[i] <= target则candidates[i]可以作为一个加数，否则，candidates[i]不能作为一个加数，且candidates[i]之后的值也不能作为加数，并退出循环。 2.当满足candidates[i] <= target时，判断当前加数是否小于求和数组中最大元素，以避免在结果数组中出现重复，若candidates[i] >= v.back(),更新target为target-candidates[i]，并将candidates[i]加入到求和数组v中。递归执行。 3.当target==0时，求和数组v中的所有元素相加正好等于所求的和，将v加入到结果数组res中。 代码：

class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); aux(candidates,target,vector<int>{}); return res; } void aux(vector<int>& candidates, int target,vector<int> v) { if(target==0){ res.push_back(v); return; } for(int i=0;i<candidates.size();++i) { if(candidates[i]<=target) { if(v.empty() || v.back()<=candidates[i]){ v.push_back(candidates[i]); aux(candidates,target-candidates[i],v); v.pop_back(); } } else break; } } vector<vector<int>> res; };