1 题目

组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。 解集不能包含重复的组合。 示例 1:

输入: candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ] 示例 2:

输入: candidates = [2,3,5], target = 8, 所求解集为: [ [2,2,2,2], [2,3,3], [3,5] ]

2 Python

方法一：回溯法

小错误版本：

class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: def backtracking(index, curSum, curList): # 回溯条件 if index > len(candidates) or curSum > target: # 错误：不是>，应该是==。列表从0开始 return # 找到目标 if curSum == target: ans.append(curList) return # 考虑当前项 backtracking(index, curSum + candidates[index], curList.append(candidates[index])) # 错误：.append()不能作为输入，用+代替 # 跳过当前项，考虑下一项 backtracking(index + 1, curSum + candidates[index+1], curList.append(candidates[index+1])) # 错误：一层函数只能加一个数，所以curSum和curList不能直接加下一项 ans = [] backtracking(0, 0, []) return ans

正确版本

class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: def backtracking(index, curSum, curList): # 回溯条件 if index == len(candidates) or curSum > target: return # 找到目标 if curSum == target: ans.append(curList) return # 考虑当前项 backtracking(index, curSum + candidates[index], curList + [candidates[index]]) # 跳过当前项 backtracking(index + 1, curSum, curList) ans = [] backtracking(0, 0, []) return ans