以下是 LeetCode 39. 组合总和 的 Rust 实现采用 回溯法DFS通过排序和剪枝优化效率。思路回溯搜索从 candidates 中不断选取数字直到当前和等于 target 或超过 target。允许重复使用递归时传递的起始索引 start 不变表示可以继续选择当前数字。避免重复组合只从 start 开始向后遍历保证组合内数字是非递减顺序从而避免产生 [2,3] 和 [3,2] 这类重复。剪枝优化提前对数组排序当当前数字加上已累积和超过 target 时直接 break 循环因为后续数字更大也不可能满足。代码实现implSolution{pubfncombination_sum(candidates:Veci32,target:i32)-VecVeci32{letmutcandidatescandidates;candidates.sort();// 排序便于剪枝letmutresVec::new();letmutpathVec::new();Self::backtrack(candidates,target,0,mutpath,mutres);res}fnbacktrack(candidates:[i32],remain:i32,start:usize,path:mutVeci32,res:mutVecVeci32,){ifremain0{res.push(path.clone());// 找到一个组合拷贝当前路径return;}foriinstart..candidates.len(){letnumcandidates[i];ifnumremain{break;// 剪枝当前数字已经大于剩余目标值后续更大}path.push(num);// 选择当前数字Self::backtrack(candidates,remain-num,i,path,res);// starti 允许重复使用path.pop();// 回溯撤销选择}}}复杂度分析· 时间复杂度O(S)其中 S 为所有可行解的长度之和。最坏情况下组合数量可能非常大但剪枝能有效减少搜索。理论上最坏为指数级但题目数据规模通常较小。· 空间复杂度O(target)递归深度最大为 target / min(candidates)全部选最小数字额外空间用于递归栈和临时路径 path。说明· 递归函数 backtrack 的参数· candidates排序后的候选数组切片。· remain还需要凑的目标和。· start当前搜索的起始索引保证组合中数字非递减同时允许重复使用i 而不是 i1。· path当前尝试的组合路径。· res存储所有合法组合的结果向量。· 当 remain 0 时将当前路径克隆后加入结果。· 循环中若 num remain由于数组已排序后续数字只会更大因此直接跳出循环。· 使用 path.clone() 因为 path 是可变引用之后还会被修改需要复制一份保存。
