leetcode 39. 组合总和

**组合总和**

给定一个非负整数数组 `candidates` 和一个目标整数 `target`，找出所有可能的组合总和，使得它们的总和等于 `target`。

**示例1:**

输入：`candidates = [2,3,6,7]`, `target =7`
输出：`[[2,2,3],[7]]`

**示例2:**

输入：`candidates = [2,3,5]`, `target =8`
输出：`[[2,2,2,2],[2,3,3],[3,5]]`

**示例3:**

输入：`candidates = [2]`, `target =1`
输出：`[]`

**解决方案**

我们可以使用回溯法来解决这个问题。回溯法是一种递归的方法，用于遍历所有可能的组合。

class Solution:
 def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
 # 初始化结果列表 result = []
 # 定义一个函数来进行回溯 def backtrack(remain, comb, start):
 # 如果剩余值等于0，说明找到了一种组合方式 if remain ==0:
 result.append(list(comb))
 return # 遍历候选数字 for i in range(start, len(candidates)):
 # 如果当前数字大于剩余值，可以跳过 if candidates[i] > remain:
 break # 添加当前数字到组合中 comb.append(candidates[i])
 # 递归进行下一步 backtrack(remain - candidates[i], comb, i)
 # 回溯，移除最后添加的数字 comb.pop()
 # 开始回溯 backtrack(target, [],0)
 return result

solution = Solution()
print(solution.combinationSum([2,3,6,7],7)) # [[2,2,3],[7]]
print(solution.combinationSum([2,3,5],8)) # [[2,2,2,2],[2,3,3],[3,5]]
print(solution.combinationSum([2],1)) # []