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]);
                }
            }
        }
    }
};