以下是 LeetCode 40. 组合总和 II 的 Rust 实现采用 回溯法DFS结合排序和去重剪枝确保每个数字只使用一次且结果无重复。思路排序先对 candidates 排序方便去重和剪枝。回溯搜索从起始索引 start 开始遍历每次选择一个数字加入路径递归处理剩余目标和。每个数字只能使用一次递归时传入 i 1 作为下一层起点避免重复使用同一元素。去重在每一层的循环中如果当前数字与前一个数字相同且是同一层的候选即 i start则跳过防止产生重复组合。剪枝若当前数字大于剩余目标值直接跳出循环因为数组已排序。代码实现implSolution{pubfncombination_sum2(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(){// 去重跳过同一层中相同的数字ifistartcandidates[i]candidates[i-1]{continue;}letnumcandidates[i];ifnumremain{break;// 剪枝当前数字已经大于剩余目标后续更大}path.push(num);Self::backtrack(candidates,remain-num,i1,path,res);// i1 保证每个数字只使用一次path.pop();}}}复杂度分析· 时间复杂度最坏情况下 O(2^n)n 为候选数组长度。但排序后剪枝和去重能大幅减少实际搜索空间。· 空间复杂度O(target)递归栈深度最大为 target / min(candidates)全部选最小数字额外存储路径。说明· 排序是去重和剪枝的前提。· 去重关键if i start candidates[i] candidates[i - 1] { continue; }这保证了在同一层递归中相同数值的元素只被考虑一次避免产生如 [1,2,5] 和 [1,2,5] 这类重复组合当数组中有多个 1、2 时。· 每个数字只使用一次递归传递的起始索引为 i 1确保不会回头选取已使用的元素。· 返回结果时使用 path.clone() 复制当前路径因为 path 在后续回溯中会被修改。