深搜练习(组合总和)(7)
一.题目
39. 组合总和 - 力扣（LeetCode）
二.思路讲解
2.1 思路讲解
本题与之前组合问题的核心区别在于：同一个数字可以被无限重复选取。这意味着在递归过程中，我们不能像之前那样用i+1强制跳过当前元素，而应该允许继续选择当前元素。因此，递归调用时，下一层的pos参数不增加（仍从i开始），这样才能重复使用同一数字。
另一个重要区别是剪枝策略：由于可以重复选取，我们需要防止无效的无限递归。可以在递归过程中检查当前累积和sum是否已经超过target，一旦超过，就可以立即剪枝（因为后续元素更大，和只会更大），无需继续探索。
递归框架：使用深度优先搜索，每层遍历从pos开始到末尾的元素，对于每个元素，将其加入路径，递归调用时传入相同的pos（允许重复），并更新和为sum + candidates[i]。当sum == target时，将当前路径加入结果并返回；当sum > target时，直接剪枝返回。这样就能枚举所有不重复的组合（因为通过pos参数保证了元素选取的顺序性，避免了[2,3]和[3,2]重复）。排序后剪枝更高效，但即使不排序，算法依然正确。
三.代码演示
class Solution { public: vector<vector<int>> ret; vector<int>path; vector<vector<int>> combinationSum(vector<int>& candidates, int target) { dfs(candidates,target,0,0); return ret; } void dfs(vector<int>& candidates,int target,int sum,int pos) { //递归终止情况 if(sum == target) { ret.push_back(path); return; } if(sum > target || pos >= candidates.size()) return; for(int i = pos;i < candidates.size();i++) { path.push_back(candidates[i]); dfs(candidates,target,sum + candidates[i],i);//因为可以选择重复的因此i不能加1 path.pop_back(); } } };四.代码讲解
一、全局变量设计
为了实现回溯，我们定义两个成员变量：
ret：二维向量，存储所有满足条件的组合结果。path：一维向量，记录当前正在构建的组合。
二、主函数combinationSum
主函数接收候选数组candidates和目标值target，调用递归函数dfs(candidates, target, 0, 0)开始深度优先搜索，最后返回结果集ret。参数含义：
sum：当前路径中所有元素的和，初始为 0。pos：当前可以从candidates的哪个下标开始选取元素，初始为 0。
三、递归函数dfs
递归函数dfs(candidates, target, sum, pos)的含义是：当前已经选择了若干元素（存储在path中），和为sum，接下来可以从下标pos开始继续选择元素，目标是使总和等于target。执行流程如下：
四、递归终止条件
成功终止：当
sum == target时，说明当前路径的和恰好等于目标值，将path的副本加入ret，然后返回。失败终止（剪枝）：当
sum > target或pos >= candidates.size()时，说明当前路径和已超过目标，或者没有更多元素可选，直接返回，不再继续探索。
五、递归步骤分解
使用for循环，从i = pos到i < candidates.size()，依次考虑每个候选元素：
将
candidates[i]加入path末尾。递归调用
dfs(candidates, target, sum + candidates[i], i)。注意，这里传入的pos参数是i而不是i+1，因为同一个元素可以被无限重复选取，所以下一层仍然可以从当前下标开始，允许重复使用。递归返回后，执行回溯：将
path末尾的元素弹出，以便尝试下一个元素。
六、回溯与恢复现场
由于path是全局变量，不同分支共享状态，因此必须在递归返回后手动恢复现场。
七、关键细节
重复选取的实现：递归调用时
pos参数传入i而不是i+1，使得下一层可以继续选择当前元素，从而允许无限次重复。剪枝优化：在递归入口处检查
sum > target，一旦超过则立即返回，避免无效的深度递归，提高了效率。避免重复组合：通过
pos参数控制选择范围，每次只能从当前或之后的下标开始，保证了组合的无序性（不会出现[2,3]和[3,2]重复）。