以下是 LeetCode 39. 组合总和 的 C 实现采用 回溯法DFS通过排序和剪枝优化效率。思路回溯搜索从 candidates 中不断选取数字直到当前和等于 target 或超过 target。允许重复使用递归时传递的起始索引 start 不变表示可以继续选择当前数字。避免重复组合只从 start 开始向后遍历保证组合内数字是非递减顺序从而避免产生 [2,3] 和 [3,2] 这类重复。剪枝优化提前对数组排序当当前数字加上已累积和超过 target 时直接 break 循环因为后续数字更大也不可能满足。代码实现#includevector#includealgorithmusingnamespacestd;classSolution{public:vectorvectorintcombinationSum(vectorintcandidates,inttarget){vectorvectorintres;vectorintpath;sort(candidates.begin(),candidates.end());// 排序便于剪枝backtrack(candidates,target,0,path,res);returnres;}private:voidbacktrack(vectorintcandidates,intremain,intstart,vectorintpath,vectorvectorintres){if(remain0){res.push_back(path);// 找到一个组合拷贝当前路径return;}for(intistart;icandidates.size();i){intnumcandidates[i];if(numremain){break;// 剪枝当前数字已经大于剩余目标值后续更大}path.push_back(num);// 选择当前数字backtrack(candidates,remain-num,i,path,res);// starti 允许重复使用path.pop_back();// 回溯撤销选择}}};复杂度分析· 时间复杂度O(S)其中 S 为所有可行解的长度之和。最坏情况下组合数量可能非常大但剪枝能有效减少搜索。理论上最坏为指数级但题目数据规模通常较小。· 空间复杂度O(target)递归深度最大为 target / min(candidates)全部选最小数字额外空间用于递归栈和临时路径 path。说明· 递归函数 backtrack 的参数· candidates排序后的候选数组引用传递。· remain还需要凑的目标和。· start当前搜索的起始索引保证组合中数字非递减同时允许重复使用i 而不是 i1。· path当前尝试的组合路径。· res存储所有合法组合的结果向量。· 当 remain 0 时将当前路径加入结果push_back(path) 会复制一份。· 循环中若 num remain由于数组已排序后续数字只会更大因此直接跳出循环。