题目描述给定一个无重复元素的整数数组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 输出: []解题思路总览方法时间复杂度空间复杂度说明回溯O(分支数^深度)O(n)经典解法指数级动态规划O(n*target)O(n*target)先算所有可达和再回溯组合排序剪枝O(分支数^深度)O(n)排序后提前终止无效分支为什么用回溯元素可以重复使用 → 下层仍从当前 index 开始需要所有组合 → 枚举而不是最优组合问题天然树状结构 → 回溯最直观完整代码方法一回溯推荐classSolution{public:vectorvectorintcombinationSum(vectorintcandidates,inttarget){vectorintpath;vectorvectorintans;autotraversal[](autoself,intsum,intindex)-void{if(sumtarget)return;if(sumtarget){ans.push_back(path);return;}for(intiindex;icandidates.size();i){path.push_back(candidates[i]);self(self,sumcandidates[i],i);// 注意传 i 不是 i1path.pop_back();}};traversal(traversal,0,0);returnans;}};方法二排序 剪枝优化classSolution{public:vectorvectorintcombinationSum(vectorintcandidates,inttarget){sort(candidates.begin(),candidates.end());// 先排序vectorintpath;vectorvectorintans;autotraversal[](autoself,intsum,intindex)-void{if(sumtarget)return;if(sumtarget){ans.push_back(path);return;}for(intiindex;icandidates.size();i){if(sumcandidates[i]target)break;// 剪枝已排序后面更大path.push_back(candidates[i]);self(self,sumcandidates[i],i);path.pop_back();}};traversal(traversal,0,0);returnans;}};算法流程图[开始] | [初始化 path, ans] | [递归 traversal(0, 0)] | [sum target?] | / 是 \ / 否 / \ 返回 [sum target?] | / 是 \ / 否 / \ 保存结果 [遍历 i从index到n-1] 返回 | [path.push(candidates[i])] | [递归 traversal(sumcandidates[i], i)] | [path.pop()] | [继续遍历下一个i] | [返回结果]决策树图解candidates[2,3,5], target8[根: sum0] / | \ 2 3 5 - 第一层选哪个数 | | | [2] [3] [5] - path状态 / \ | 2 3 2 | | | [2,2] [2,3] [3,2] | | | ... ... ... 完整展开只展示部分: [2,2,2,2] - sum8 保存 [2,2,3] - sum9 8 剪枝 [2,3,3] - sum8 保存 [3,5] - sum8 保存 [5,5] - sum10 8 剪枝逐行解析1. 边界条件if(sumtarget)return;// 剪枝超过目标无效if(sumtarget){ans.push_back(path);// 找到一组解return;}关键剪枝sum 超过 target 时直接返回不继续递归sum 等于 target 时保存结果返回不能继续选数了2. 核心循环for(intiindex;icandidates.size();i){path.push_back(candidates[i]);self(self,sumcandidates[i],i);// 传 i允许重复选当前数path.pop_back();}核心区别self(self, ..., i)传的是i而非i1这允许同一元素被无限次选取index参数控制组合的起始点保证不重复3. 为什么 index 参数避免重复如果不加 indexcandidates[2,3], target8 第一层选2 - 第二层选2 - [2,2,2,2] OK 第一层选3 - ...会产生 [3,2,3] 等组合 加上 index 后 第一层从 index0 开始选 选2后递归传 i0第二层还是从0开始选允许重复 但不会跨过2去选3开头的组合因为我们是按顺序选的 实际上 index 保证了每层递归只能从当前位置或之后选 这样 [2,3] 和 [3,2] 就不会都出现了详细 trace 演示以 candidates[2,3,5], target8 为例traversal(0, 0) | -- i0, 选2, path[2], sum2 | | | -- i0, 选2, path[2,2], sum4 | | | | | -- i0, 选2, path[2,2,2], sum6 | | | | | | | -- i0, 选2, path[2,2,2,2], sum8 - 保存 | | | -- i1, 选3, sum9 8 返回 | | | -- i2, 选5, sum11 8 返回 | | -- i1, 选3, path[2,2,3], sum7 | | | | | | | -- i0, 选2, sum9 8 返回 | | | -- i1, 选3, sum10 8 返回 | | | -- i2, 选5, sum12 8 返回 | | -- i2, 选5, path[2,2,5], sum9 8 返回 | -- i1, 选3, path[2,3], sum5 | | | | | -- i0, 选2, path[2,3,2], sum7 | | | | | | | -- i0, 选2, sum9 8 返回 | | | -- i1, 选3, sum10 8 返回 | | | -- i2, 选5, sum12 8 返回 | | -- i1, 选3, path[2,3,3], sum8 - 保存 | | -- i2, 选5, sum10 8 返回 | -- i2, 选5, path[2,5], sum7 | | | -- ... 8 全部返回 -- i1, 选3, path[3], sum3 | | | -- i0, 选2, path[3,2], sum5 | | | | | -- ... 全部 8 返回 | -- i1, 选3, path[3,3], sum6 | | | | | -- ... 全部 8 返回 | -- i2, 选5, path[3,5], sum8 - 保存 -- i2, 选5, path[5], sum5 | -- ... 全部 8 返回 最终保存[[2,2,2,2], [2,3,3], [3,5]]复杂度分析时间复杂度O(分支数^深度)最坏情况target 很大candidates 最小为 2递归树节点数 2^n 量级指数级题目保证结果少于 150 个组合target最小组合数candidates[2]最多约302^30 ≈ 10亿指数级空间复杂度O(n)递归栈最大深度 ≤ target/min(candidates)path 存储当前路径常见错误错误1index 传错了// 错误index1 导致不能重复选同一元素self(self,sumcandidates[i],i1);// 正确index 保持不变允许重复选self(self,sumcandidates[i],i);错误2少了剪枝// 错误少了 sum target 的判断会多遍历无效分支if(sumtarget){...}for(...){...}// 正确加上 sum target 的剪枝if(sumtarget)return;if(sumtarget){...}for(...){...}错误3结果重复没有 index 参数// 错误如果没有 index 参数会产生 [2,3] 和 [3,2] 两种重复组合for(inti0;icandidates.size();i){self(self,sumcandidates[i],i1);// 这会产生重复}// 正确index 参数控制起点保证不重复for(intiindex;icandidates.size();i){self(self,sumcandidates[i],i);}面试追问 FAQ问题回答为什么可以重复选因为题目没有限制每个元素只能用一次怎么保证不产生重复组合通过 index 参数控制起点每次从当前或之后的元素选不会回头剪枝怎么做的sum target 时直接返回不继续递归能 用 DP 吗可以但 DP 更适合求「是否存在」组合问题用回溯更直接如何输出字典序对 candidates 排序后回溯自然按字典序排序后怎么剪枝如果 sum candidates[i] target因为已排序后面的数更大直接 break相关题目对比题目难度核心区别40. 组合总和 II中等每个元素只能用一次需要去重216. 组合总和 III中等选 k 个数和为 n377. 组合总和 IV中等顺序不同的组合算不同排列剑指II 081. 允许重复选择元素的组合求和中等本题原题举一反三回溯问题的通用模板voidbacktrack(参数){if(终止条件){收集结果;return;}for(选择:本层选择列表){做选择;backtrack(下一层参数);撤销选择;}}三要素路径已经做出的选择选择列表当前可做的选择终止条件达到目标满足要求本题的关键点要点说明重复选index 传 i 而不是 i1不重复index 参数控制起点剪枝sum target 直接返回总结要点说明核心思想回溯 剪枝关键参数sum当前和、index起始位置重复选择传 i 而非 i1剪枝条件sum target去重机制index 参数控制起点保证有序不重复时间复杂度指数级空间复杂度O(n)完整测试代码#includeiostream#includevectorusingnamespacestd;classSolution{public:vectorvectorintcombinationSum(vectorintcandidates,inttarget){vectorintpath;vectorvectorintans;autotraversal[](autoself,intsum,intindex)-void{if(sumtarget)return;if(sumtarget){ans.push_back(path);return;}for(intiindex;icandidates.size();i){path.push_back(candidates[i]);self(self,sumcandidates[i],i);path.pop_back();}};traversal(traversal,0,0);returnans;}};intmain(){Solution s;vectorpairvectorint,inttests{{{2,3,6,7},7},{{2,3,5},8},{{2},1}};for(auto[candidates,target]:tests){coutcandidates [;for(inti0;icandidates.size();i){coutcandidates[i];if(icandidates.size()-1)cout,;}cout], target targetendl;vectorvectorintanss.combinationSum(candidates,target);cout输出: [;for(inti0;ians.size();i){cout[;for(intj0;jans[i].size();j){coutans[i][j];if(jans[i].size()-1)cout,;}cout];if(ians.size()-1)cout,;}cout]endlendl;}return0;}运行结果candidates [2,3,6,7], target 7 输出: [[2,2,3],[7]] candidates [2,3,5], target 8 输出: [[2,2,2,2],[2,3,3],[3,5]] candidates [2], target 1 输出: []