class Solution {
public:
    void backtrack(vector<int>& nums, int target, vector<int>& curr, vector<vector<int>>& sol, int last_pos) {
        if (target < 0) return;
        if (target == 0) {
            sol.push_back(curr);
            return;
        }
        for (int i = last_pos; i < nums.size(); i++) {
            curr.push_back(nums[i]);
            backtrack(nums, target-nums[i], curr, sol, i);
            curr.pop_back();
        }

    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> sol;
        vector<int> curr;
        backtrack(candidates, target, curr, sol, 0);
        return sol;
    }
};