Leetcode题39、组合总和（Python题解）

问题：

题目来源：力扣（LeetCode）

leetcode39.组合总和

难度：中等

分析： 回溯法，与组合的解法类似。需要注意的是，本题中元素可以重复使用，因此向下回溯的时候不能直接向后挪动index，而要包含当前元素。 再加一个判断条件，当路径总和小于等于目标值时，向下回溯。注意要加等号，因为在下一层才能判断路径和是否等于目标值，当当前路径和等于target时需要有机会向下递归。

解决方法： 1：回溯法

class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: if candidates == []: return [[]] def backtrack(index): if sum(path) == target: res.append(path[:]) for i in range(index, len(candidates)): path.append(candidates[i]) if sum(path) <= target: backtrack(i) path.pop() path = [] res = [] backtrack(0) return res