以下是 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):ifremain==0:# 找到一个组合res.append(path[:])# 拷贝当前路径returnforiinrange(start,len(candidates)):num=candidates[i]ifnum>remain:# 剪枝：当前数字已经大于剩余目标值breakpath.append(num)# 选择当前数字backtrack(i,path,remain-num)# 注意 start=i，允许重复使用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 提前终止循环，减少不必要的递归。
