Description
Submission
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
combinationSumUtil(res, candidates, {}, target);
return res;
}
private:
void combinationSumUtil(vector<vector<int>>& res, vector<int>& candidates, vector<int> tmp, int target) {
for(int i = 0; i < candidates.size(); ++i) {
if(target == candidates[i]) {
if(tmp.empty() || (!tmp.empty() && *prev(tmp.end()) <= target)) {
vector<int> t = tmp;
t.push_back(target);
res.push_back(t);
}
}
if(target - candidates[i] > 0) {
if(tmp.empty() || (!tmp.empty() && *prev(tmp.end()) <= candidates[i])) {
vector<int> t = tmp;
t.push_back(candidates[i]);
combinationSumUtil(res, candidates, t, target - candidates[i]);
}
}
}
}
};