XingHuiSama の宝藏之地

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

‍

1. 算法核心思想

本题是一道经典的回溯算法（Backtracking）题目。由于题目允许同一个数字被无限制重复选取，如果不加限制地暴力搜索，极易导致搜索树过于庞大甚至引发栈溢出。

为了极致提升运行效率，本段代码采用了“回溯 + 排序剪枝”的策略：

核心思路：把寻找组合的过程看作是在遍历一棵多叉树。我们维护一个当前路径 temp 和当前路径和 sum。
高阶优化（剪枝）：在开始搜索前，先将原数组升序排序。在回溯过程中，一旦发现当前的 sum 已经大于或等于 target，由于后面的元素比当前元素更大，继续向后探索绝对不可能凑出 target。此时果断触发 return（或 break），直接砍掉整棵无效的子树。这就是算法中常说的“剪枝”艺术。

2. 代码逻辑拆解

第一阶段：前置排序与入口 在主函数中，首先执行 sort(candidates.begin(), candidates.end());。这是后续能够进行高效剪枝的大前提。随后初始化结果集 res 和路径集 v，并以起点 k = 0 进入递归。
第二阶段：做选择与状态叠加 进入 for 循环后，遍历从 k 开始的备选数字。使用 sum += candidates[i] 累加当前和，用 temp.push_back() 将当前数字收入篮子。
第三阶段：精准的终止与剪枝 (Pruning) 代码在这里展现了极高的效率：
命中目标：如果 sum == target，说明刚好凑齐！将其存入 res，然后回溯恢复状态，并立刻 return。因为数组递增，后面的数字加上去必然大于 target，无需再看。
超载剪枝：如果 sum > target，说明当前组合已经爆了。同样回溯恢复状态后直接 return，砍掉后续所有更糟糕的尝试。
第四阶段：深度探索与回溯 如果当前 sum < target，则安安稳稳地调用 func(..., i) 进入下一层。注意这里传入的是 i 而不是 i + 1，巧妙地实现了“当前数字可以被无限制重复选取”的题目要求。从下一层退回来后，严格执行 sum -= candidates[i] 和 temp.pop_back()，把吃进去的吐出来，保证下一次循环的干净状态。

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        // 核心优化：先升序排序，为后续的“剪枝”铺平道路
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> res;
        vector<int> v;
        func(candidates, target, res, v, 0, 0);
        return res;
    }

    void func(vector<int>& candidates, int target, vector<vector<int>> &res, vector<int> &temp, int sum, int k) {
        for (int i = k; i < candidates.size(); i++) {
            sum += candidates[i];
            temp.push_back(candidates[i]);

            // 剪枝 1：刚好凑齐，记录结果后直接结束当前深度的后续遍历
            if (sum == target) {
                res.push_back(temp);
                temp.pop_back();
                sum -= candidates[i];
                return;
            }
            // 剪枝 2：已经超载，由于数组递增，后面的数字只会更大，直接结束遍历
            if (sum > target) {
                sum -= candidates[i];
                temp.pop_back();
                return;
            }

            // 尚未达到 target，继续深入探索。注意传的是 i，允许重复选取
            func(candidates, target, res, temp, sum, i);

            // 撤销选择（回溯的灵魂），去尝试下一个兄弟节点
            sum -= candidates[i];
            temp.pop_back();
        }
    }
};

3. 复杂度分析

时间复杂度： $\mathcal{O}(S \times 2^N)$ （由于剪枝的存在，实际运行时间远低于理论最坏值）。最坏情况下，我们要探索所有可能的组合。决定时间复杂度的主要是递归树的节点数，其高度最大为 $\frac{target}{\min(candidates)}$ 。有了排序剪枝后，我们在遇到不合法的分支时会提前终止，大幅削减了无效的搜索时间。
空间复杂度： $\mathcal{O}(\frac{target}{\min(candidates)})$

空间开销主要取决于系统递归栈的深度。在最坏情况下（比如 candidates 包含 1，我们要凑 100），递归树的最长路径即为 $target$ 除以数组中的最小元素。除此之外，仅有 temp 数组占用与递归深度等量的线性空间。

‍