LeetCode 39. 组合总和

题目描述

39. 组合总和

解法

这道题超级简单，如果你看过 LeetCode 77. 组合 这篇的解法，你肯定知道 backtrace 时 $i$ 都是从 $start$ 开始，那么下一层回溯树就是从 $start+1$ 开始，从而保证 $nums[start]$ 这个元素不会被重复使用

// 回溯算法标准框架
for (int i = start; i < nums.size(); i++) {
    
    // ...
    // 递归遍历下一层回溯树，注意参数
    backtrack(nums, i + 1, target);
    // ...
}

但是，我们现在希望能够重复使用 $nums[start]$ 这个元素，那么很好办嘛，我只要把 $i+1$ 改成 $i$ 即可

// 回溯算法标准框架
for (int i = start; i < nums.size(); i++) {
    
    // ...
    // 递归遍历下一层回溯树
    backtrack(nums, i, target);
    // ...
}

下面是完整实现

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