LeetCode 39. 组合总和

题目描述

39. 组合总和

解法

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

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

但是，我们现在希望能够重复使用 n u m s [ s t a r t ] nums[start] nums[start] 这个元素，那么很好办嘛，我只要把 i + 1 i + 1 i+1 改成 i i 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];
        }
    }
};