📝 题目描述

题目链接：组合总和

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

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

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

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
示例 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

💡 解题思路

方法一：回溯

套用回溯的模板解法即可。

遍历每个数字，如果 target > candidates[i]，则可以将其加入排好的序列并继续递归，直到找到 target = candidates[i] 的数字。

这里需要注意一点，由于题目中说一个数字可以重复选择，而为了避免“[2, 3, 3]”和“[3, 2, 3]”这种重复答案入选，我们可以设置一个 index ，递归时只允许从 index 开始选择数字，即可做到不重不漏。

🔧 代码实现

1、回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    vector<vector<int>> res;

    void backtrack(vector<int>& candidates, int target, vector<int>& track, int startIndex) {
        // 当目标值减到 0 时，说明找到了一个有效组合
        if (target == 0) {
            res.push_back(track);
            return;
        }

        // 从 startIndex 开始遍历，避免产生重复组合
        for (int i = startIndex; i < candidates.size(); i++) {
            if (target < candidates[i]) {
                continue; 
            }

            // 1. 做选择
            track.push_back(candidates[i]);
            
            // 2. 递归探底：因为元素可以无限制重复被选取，所以传入的仍然是 i，而不是 i + 1
            backtrack(candidates, target - candidates[i], track, i);
            
            // 3. 撤销选择（状态恢复）
            track.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> track;
        // 初始 startIndex 传 0
        backtrack(candidates, target, track, 0);
        return res;
    }
};

📊 复杂度分析

1、回溯

  • 时间复杂度：O(ntargetmin_val)O(n^{\frac{target}{min\_val}})，回溯算法的时间复杂度主要取决于搜索树的节点总数。我们可以通过分析这棵搜索树的“深度”和“宽度”来得出结论。对于深度，由于同一个数字可以被无限制重复选取，最坏的情况是我们一直贪心地选择数组中最小的那个元素（min_valmin\_val）；对于宽度，在树的每一层，我们理论上最多可以遍历 nn 个子节点（即 candidates 中的 nn 个数字）。
  • 空间复杂度：O(ntargetmin_val)O(n^{\frac{target}{min\_val}})，递归到达最深处的情况是一直选择最小元素 min_valmin\_val，此时栈的深度为 targetmin_val\frac{target}{min\_val}​。

🎯 总结

  • 核心思想：掌握回溯的模板写法。