Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
- All numbers (including
target) will be positive integers. - The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
题目链接：https://leetcode-cn.com/problems/combination-sum/
思路
回溯法，向下传递结果运行效率更高。
剪枝：对候选人做排序，这样每一次选的都是数组里最小的数值，若比目标还大，则需要剪枝。
去重：对于组合的题目，需要对同一组合不同排序的结果去重，方法就是在组合答案时只看>=自身的数字。
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
if(candidates.size()<=0) return res;
sort(candidates.begin(), candidates.end());
vector<int> cur;
trace(candidates, target, cur);
return res;
}
void trace(vector<int> candidates, int target, vector<int> &cur){
if(candidates[0]>target) return;
for(int i=0; i<candidates.size(); ++i){
if(candidates[i] > target) break;
if(cur.size()>0 && candidates[i] < cur.back()) continue;
else{
cur.push_back(candidates[i]);
if(candidates[i] == target) res.push_back(cur);
else trace(candidates, target-candidates[i], cur);
cur.pop_back();
}
}
return;
}
};