39.cpp

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> res;
        vector<int> curr;
        bk(res, candidates, curr, 0, target);
        return res;
    }
    void bk(vector<vector<int>>& ans, vector<int>& candidates, vector<int> curr, int last_use, int rest_target) {
        if (rest_target == 0) ans.push_back(curr);
        for(int i = last_use; i < candidates.size() && candidates[i] <= rest_target; i++) {
            curr.push_back(candidates[i]);
            bk(ans, candidates, curr, i, rest_target - candidates[i]);
            curr.pop_back();
        }
    }
};