题目： 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
输出: []

Tips

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

Code

代码解释

这段 C++ 代码实现了一个回溯算法，用于求解组合总和问题。给定一个数组 candidates 和一个目标值 target，需要找到所有组合，使得每个组合中的元素之和等于 target。每个元素在组合中可以被重复使用多次。

class Solution {
public:
    vector<vector<int>> ans; // 用于存储所有满足条件的组合结果
    vector<int> path; // 用于存储当前的组合路径

    // 回溯函数，用于生成组合
    void backtrack(vector<int>& candidates, int target, int index) {
        // 当 target 为 0 时，表示找到一个有效组合，将当前路径存入结果中
        if (target == 0) {
            ans.push_back(path);
            return;
        }

        // 遍历候选数组，从 index 开始
        for (int i = index; i < candidates.size(); i++) {
            // 如果当前数字大于 target，则跳出循环（剪枝）
            if (target - candidates[i] < 0) {
                return;
            } else {
                // 选择当前数字，并加入路径
                path.push_back(candidates[i]);
                // 递归调用，继续寻找组合，注意传递当前索引 i 允许重复使用当前元素
                backtrack(candidates, target - candidates[i], i);
                // 回溯，移除最后加入的元素
                path.pop_back();
            }
        }
    }

    // 主函数，初始化并调用回溯函数
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        // 排序候选数组，方便后续剪枝操作
        sort(candidates.begin(), candidates.end());
        // 调用回溯函数开始搜索
        backtrack(candidates, target, 0);
        // 返回最终结果
        return ans;
    }
};

逐行解释

vector<vector<int>> ans;:
- 用于存储所有满足条件的组合结果。
vector<int> path;:
- 用于存储当前的组合路径。
void backtrack(vector<int>& candidates, int target, int index):
- 定义了一个回溯函数，参数包括候选数组 candidates、目标和 target 以及当前递归的起始位置 index。
if (target == 0) { ans.push_back(path); return; }:
- 终止条件之一：如果 target 恰好为 0，表示找到一个符合条件的组合，将当前路径 path 添加到结果集中。
for (int i = index; i < candidates.size(); i++) { ... }:
- 遍历候选数组，从位置 index 开始，尝试所有可能的组合。
if (target - candidates[i] < 0) { return; }:
- 如果当前数字大于 target，则直接返回（剪枝操作），因为数组已排序，后续的数字只会更大。
path.push_back(candidates[i]);:
- 选择当前数字，将其加入路径。
backtrack(candidates, target - candidates[i], i);:
- 递归调用回溯函数，继续尝试减去当前数字后的新目标值。传递 i 允许重复使用当前元素。
path.pop_back();:
- 回溯操作，移除最后一个加入的数字，尝试其他可能的组合。
vector<vector<int>> combinationSum(vector<int>& candidates, int target):
- 主函数，首先对候选数组进行排序，然后调用回溯函数开始搜索，最后返回结果。