【回溯-3】39.组合总和

题目描述：

给你一个 无重复元素 的整数数组 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
输出: []

解题思路：

方法一：回溯 + 剪枝

核心思路：

把问题看成树形结构：

• 每一层选择一个数字

• 可以重复选同一个数字

• 当和等于 target 时，收集结果

• 当和大于 target 时，剪枝

关键：如何避免重复组合？

用 start 参数控制选择范围：

• 每次递归时，从 start 开始遍历

• 选了 candidates[i] 后，下一层从 i 开始（允许重复选当前数字）

• 但不能选 i 之前的数字（避免重复组合）

具体过程示例：

candidates = [2,3,6,7], target = 7

                    []
          /    /     \     \
         2    3       6     7
        /|\   |\      |
       2 3 6  3 6     6
      /|\  |   |
     2 3 6 3  6  6
     |
     2(和=8>7，剪枝)

有效路径:
2→2→3 (和=7) ✅
7 (和=7) ✅

代码实现：

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> path;
        backtrack(candidates, target, 0, path, result);
        return result;
    }
    
private:
    void backtrack(vector<int>& candidates, int target, int start,
                   vector<int>& path, vector<vector<int>>& result) {
        // 终止条件：和等于 target
        if (target == 0) {
            result.push_back(path);
            return;
        }
        
        // 剪枝：和小于 0，直接返回
        if (target < 0) return;
        
        // 从 start 开始遍历，避免重复组合
        for (int i = start; i < candidates.size(); i++) {
            path.push_back(candidates[i]);           // 选择
            backtrack(candidates, target - candidates[i], i, path, result);  // 递归，注意传 i 而不是 i+1
            path.pop_back();                          // 撤销
        }
    }
};

复杂度分析：

设 n 是候选数组长度，target 是目标和。

维度	复杂度	说明
时间复杂度	O(n^(target/min)))	最坏情况，每个位置可以选 n 个数字
空间复杂度	O(target/min)	递归栈深度 + path 长度

更精确：时间复杂度与解的数量和递归深度有关，最坏情况为指数级。

关键细节：

1. 为什么递归时传 i 而不是 i+1？

• 传 i：允许重复选当前数字（如 [2,2,3]）

• 传 i+1：不允许重复选（如 40 题「组合总和 II」）

这是本题和 40 题的核心区别。

2. 为什么用 start 参数？

start 控制当前层从哪个位置开始遍历，避免产生重复组合。

例子：candidates = [2,3], target = 5

• 如果不用 start：[2,3] 和 [3,2] 都会出现，重复

• 用 start：选了 2 后，下一层只能从 2 开始（含 2），不能选 3 之前的

3. 为什么 target < 0 要返回？

因为和已经超过 target，继续加只会更大，直接剪枝。

4. 排序优化（可选）

如果先对 candidates 排序，可以在 target < candidates[i] 时提前 break：

sort(candidates.begin(), candidates.end());
// ...
for (int i = start; i < candidates.size(); i++) {
    if (target < candidates[i]) break;  // 后面的更大，直接结束
    // ...
}

方法二：动态规划（完全背包）

代码实现：

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<vector<int>>> dp(target + 1);
        dp[0] = {{}};
        
        for (int c : candidates) {
            for (int j = c; j <= target; j++) {
                for (auto& comb : dp[j - c]) {
                    vector<int> newComb = comb;
                    newComb.push_back(c);
                    dp[j].push_back(newComb);
                }
            }
        }
        
        return dp[target];
    }
};

复杂度：时间 O(n × target × 解的数量)，空间 O(target × 解的数量)

缺点：需要存储所有中间结果，空间大。

两种方法对比：

方法	时间复杂度	空间复杂度	推荐度
回溯 + 剪枝	指数级	O(target/min)	⭐⭐⭐⭐⭐
动态规划	O(n × target × 解的数量)	O(target × 解的数量)	⭐⭐⭐

总结：

要点	说明
核心思想	回溯：从 start 开始遍历，可以重复选当前数字
关键条件	递归时传 i（允许重复），用 start 避免重复组合
终止条件	target == 0 收集结果，target < 0 剪枝
时间复杂度	指数级
空间复杂度	O(target/min)

 

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/m0_73352944/article/details/166940875