leetcode39.组合总和

题目

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40

解答

基础回溯法

本题的搜索过程可以抽象成如下树形结构：

39.组合总和

使用回溯三步曲：

递归函数的参数

定义一个二维数组results用于存储最终的组合，定义一个一维数组用于存储单次组合。这两个变量为全局变量，然后定义一个递归函数traceback,它的参数为题目自带的候选数组canditate，target，以及path元素的和sum，以及开始遍历的索引startIndex

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex)

递归终止条件

当sum>target时，没有继续遍历下去的必要，当sum==target时将当前的path放进results中，并退出当前递归函数。

if (sum > target) {
    return;
}
if (sum == target) {
    result.push_back(path);
    return;
}

单层搜索逻辑

从startIndex开始遍历candidates数组，搜索组合

for (int i = startIndex; i < candidates.size(); i++) {
    sum += candidates[i];
    path.push_back(candidates[i]);
    backtracking(candidates, target, sum, i); // 关键点:不用i+1了，表示可以重复读取当前的数
    sum -= candidates[i];   // 回溯
    path.pop_back();        // 回溯
}

整个代码：

class Solution {
private:
    vector<vector<int>> results;
    vector<int> path;
    void tracebacking(vector<int> candidates, int target, int sumValue,int startIndex) {
        //参数分别为候选数组，目标值，path中元素的和sumValue，最终结果results，单个组合path，开始遍历的索引startIndex
        if (sumValue > target) return; // 如果sumValue比target大，直接剪枝
        // 终止条件
        if (sumValue == target) {
            // 符合一个组合的条件
            results.push_back(path);
            return;
        }
        for (int i = startIndex; i < candidates.size();i++) {
            path.push_back(candidates[i]);
            sumValue += candidates[i];
            tracebacking(candidates, target, sumValue, i);
            // 回溯
            path.pop_back();
            sumValue -= candidates[i];
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        results.clear();
        path.clear();
        tracebacking(candidates, target, 0, 0);
        return results;   
    }
};

剪枝优化

对数组进行排序，在for循环中的判断中增加一个判断，可以进行有效的剪枝。

class Solution {
private:
    vector<vector<int>> results;
    vector<int> path;
    void tracebacking(vector<int> candidates, int target, int sumValue,int startIndex) {
        //参数分别为候选数组，目标值，path中元素的和sumValue，最终结果results，单个组合path，开始遍历的索引startIndex
        if (sumValue > target) return; // 如果sumValue比target大，直接剪枝
        // 终止条件
        if (sumValue == target) {
            // 符合一个组合的条件
            results.push_back(path);
            return;
        }
        for (int i = startIndex; i < candidates.size() && sumValue + candidates[i] <= target;i++) {
            // for循环中的判断条件做了剪枝优化
            path.push_back(candidates[i]);
            sumValue += candidates[i];
            tracebacking(candidates, target, sumValue, i);
            // 回溯
            path.pop_back();
            sumValue -= candidates[i];
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        results.clear();
        path.clear();
        sort(candidates.begin(), candidates.end()); // 排序，减少不必要的计算
        tracebacking(candidates, target, 0, 0);
        return results;   
    }
};

参考链接

代码随想录：https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html