以下是 LeetCode 39. 组合总和 的 Python3 实现采用 回溯法DFS通过排序和剪枝优化效率。思路回溯搜索从 candidates 中不断选取数字直到当前和等于 target 或超过 target。允许重复使用递归时传递的起始索引 start 不变表示可以继续选择当前数字。避免重复组合只从 start 开始向后遍历保证组合内数字是非递减顺序从而避免产生 [2,3] 和 [3,2] 这类重复。剪枝优化提前对数组排序当当前数字加上已累积和超过 target 时直接 break 循环因为后续数字更大也不可能满足。代码实现classSolution:defcombinationSum(self,candidates:List[int],target:int)-List[List[int]]:res[]candidates.sort()# 排序便于剪枝defbacktrack(start,path,remain):ifremain0:# 找到一个组合res.append(path[:])# 拷贝当前路径returnforiinrange(start,len(candidates)):numcandidates[i]ifnumremain:# 剪枝当前数字已经大于剩余目标值breakpath.append(num)# 选择当前数字backtrack(i,path,remain-num)# 注意 starti允许重复使用path.pop()# 回溯撤销选择backtrack(0,[],target)returnres复杂度分析· 时间复杂度O(S)其中 S 为所有可行解的长度之和。最坏情况下组合数量可能很大但剪枝能有效减少搜索。理论上最坏为指数级但题目数据规模通常较小。· 空间复杂度O(target)递归深度最大为 target / min(candidates)全部选最小数字额外空间用于递归栈和临时路径。说明· 递归函数 backtrack(start, path, remain) 中remain 表示还需要凑的和。· 当 remain 0 时表示已找到一个合法组合将其加入结果列表。· 循环从 start 开始保证组合有序且不会回头选择更小的数从而避免重复。· 排序后使用 if num remain: break 提前终止循环减少不必要的递归。
