LeetCode 39. Combined sum

Title Description

39. Combinatorial summation

solution

This problem is super simple , If you've seen it LeetCode 77. Combine The solution of this article , You must know backtrace when $i$ from $start$ Start , So the next level of backtracking tree is from $start+1$ Start , To ensure that $nums[start]$ This element will not be reused

//  Standard framework of backtracking algorithm 
for (int i = start; i < nums.size(); i++) {
    
    // ...
    //  Recursively traverse the next level of backtracking tree , Pay attention to the parameters 
    backtrack(nums, i + 1, target);
    // ...
}

however , Now we hope to reuse $nums[start]$ This element , Then it's easy to do , I just want to $i+1$ Change to $i$ that will do

//  Standard framework of backtracking algorithm 
for (int i = start; i < nums.size(); i++) {
    
    // ...
    //  Recursively traverse the next level of backtracking tree 
    backtrack(nums, i, target);
    // ...
}

Here is the complete implementation

class Solution {
    
public:

    vector<vector<int>> res;

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    
        int trackSum;
        vector<int> track;
        backtrace(candidates, target, 0, track, trackSum);
        return res;
    }

    void backtrace(vector<int>& candidates, int target, int start, vector<int>& track, int trackSum)
    {
    
        if (trackSum == target)
        {
    
            res.push_back(track);
            return;
        }

        if (trackSum > target) return;

        for (int i = start; i < candidates.size(); i++)
        {
    
            trackSum += candidates[i];
            track.push_back(candidates[i]);
            backtrace(candidates, target, i, track, trackSum);
            track.pop_back();
            trackSum -= candidates[i];
        }
    }
};