思路:先对数据进行排序(看评论给的测试数据好像都是有序数组了,但题目里没有给出这个条件),然后回溯加剪枝即可。
class Solution {
public:
int size = ;
vector<vector<int>> ans;
void search(int pos, vector<int>& candidates, int target, vector<int>& res, int sums){
if(sums == target){
ans.push_back(res);
return;
}
if (pos >= size) return;
for(int i = pos; i < size; i++)
{
if(candidates[i] > target) return;
sums += candidates[i]; res.push_back(candidates[i]);
if(sums > target){
sums -= candidates[i];
res.pop_back();
return;
}
search(i, candidates, target, res, sums);
sums -= candidates[i];
res.pop_back();
} } vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
size = candidates.size();
vector<int> res;
if(size == ) return ans;
search(, candidates, target, res, );
return ans;
}
};