题目描述给定一个无重复元素的整数数组candidates和一个目标整数target找出candidates中可以使数字和为目标数target的所有不同组合并以列表形式返回。关键规则candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同则两种组合是不同的。保证和为target的不同组合数少于 150 个。示例 1输入candidates [2,3,6,7], target 7输出[[2,2,3],[7]]解释223777仅这两种组合。示例 2输入candidates [2,3,5], target 8输出[[2,2,2,2],[2,3,3],[3,5]]解法回溯法深度优先搜索核心思路这道题本质上是带条件的组合问题可以用回溯法解决路径记录用一个列表path保存当前正在构建的组合。和的跟踪用一个变量sum记录当前路径的和。终止条件当sum target将当前path加入结果集。当sum target直接返回剪枝。可重复选取为了避免重复组合搜索时只能从当前元素开始向后遍历不能回头这样既保证了元素可重复使用又不会出现排列重复的情况。代码实现Cclass Solution { public: vectorvectorint combinationSum(vectorint candidates, int target) { vectorvectorint res; vectorint path; backtrack(candidates, target, 0, 0, path, res); return res; } private: /** * param candidates 候选数组 * param target 目标和 * param start 本次搜索的起始位置避免重复组合 * param sum 当前路径的和 * param path 当前路径 * param res 结果集 */ void backtrack(const vectorint candidates, int target, int start, int sum, vectorint path, vectorvectorint res) { // 终止条件1和等于目标记录结果 if (sum target) { res.push_back(path); return; } // 终止条件2和超过目标剪枝 if (sum target) { return; } // 从start开始遍历避免重复组合 for (int i start; i candidates.size(); i) { // 选择当前元素 path.push_back(candidates[i]); sum candidates[i]; // 递归搜索下一层仍从i开始可重复选取 backtrack(candidates, target, i, sum, path, res); // 回溯撤销选择 sum - candidates[i]; path.pop_back(); } } };优化版排序 剪枝先对数组排序在循环中提前终止不可能的分支提高效率class Solution { public: vectorvectorint combinationSum(vectorint candidates, int target) { vectorvectorint res; vectorint path; sort(candidates.begin(), candidates.end()); // 排序 backtrack(candidates, target, 0, 0, path, res); return res; } private: void backtrack(const vectorint candidates, int target, int start, int sum, vectorint path, vectorvectorint res) { if (sum target) { res.push_back(path); return; } for (int i start; i candidates.size(); i) { if (sum candidates[i] target) break; // 剪枝后面的元素更大直接终止 path.push_back(candidates[i]); backtrack(candidates, target, i, sum candidates[i], path, res); path.pop_back(); } } };详细步骤解析以candidates [2,3,6,7], target 7为例1. 初始状态path []sum 0start 02. 第一次递归i0元素2选择2path [2]sum 2递归调用backtrackstart 0可继续选 2第二次递归i0元素2选择2path [2,2]sum 4递归调用backtrackstart 0第三次递归i0元素2选择2path [2,2,2]sum 6递归调用backtrackstart 0第四次递归选2→sum87剪枝返回回溯弹出2sum6i1选3→sum6397剪枝返回... 后续元素均大于剩余和返回回溯弹出2sum4i1选3→sum437path[2,2,3]加入结果集回溯过程弹出3sum4→ 继续遍历后续元素过大返回弹出2sum2→i1选3→sum5递归后无法凑够 7返回i2选6→sum87剪枝返回i3选7→sum97剪枝返回3. 第一次递归i1元素3选3sum3后续无法凑够 7返回i2选6sum6后续无法凑够 7返回i3选7sum7path[7]加入结果集最终结果[[2,2,3],[7]]关键知识点解析1. 为什么start参数能避免重复组合如果每次都从0开始遍历会出现[2,3]和[3,2]这样的重复组合。从start开始遍历保证了组合的元素顺序与原数组一致不会出现排列重复。同时递归时仍从i开始允许元素重复选取。2. 回溯的本质选择 - 递归 - 撤销选择选择将当前元素加入path更新sum。递归进入下一层搜索。撤销选择弹出当前元素恢复sum尝试下一个元素。3. 剪枝优化的原理对数组排序后如果当前元素candidates[i]已经大于target - sum后面的元素会更大无需继续遍历直接break。大幅减少无效递归调用提升效率。复杂度分析时间复杂度\(O(n \times 2^n)\)其中 n 是数组长度。每个元素都有选或不选两种可能最坏情况下需要遍历所有组合。空间复杂度\(O(target / min(candidates))\)递归栈深度最多为目标和除以最小元素即最长组合的长度。常见误区与注意事项忘记设置start参数会导致重复组合如[2,3]和[3,2]。递归时start设为i1会变成 “元素不可重复选取” 的组合问题不符合题意。未进行剪枝优化对于较大的target和数组会超时。总结这道题是回溯算法的经典入门题核心是理解如何用start参数控制组合顺序避免重复。如何利用排序 剪枝优化搜索效率。回溯的 “选择 - 递归 - 撤销选择” 模板。