leetcode 40. 组合总和 II

**组合总和 II**

给定一个整数数组 `candidates` 和一个目标整数 `target`，找出所有可能的组合，使得从 `candidates` 中选取数字之和等于 `target`。每个数字在每个组合中只能使用一次。

**示例1:**

输入:`candidates = [10,1,2,7,6,1,5]`, `target =8`
输出:`[[1,1,6],[1,2,5],[1,7],[2,6]]`

**示例2:**

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

**示例3:**

输入:`candidates = [2,5,8,12,15], target =10`
输出:`[]`

**解决方案**

我们可以使用回溯法来解决这个问题。回溯法是一种用于求解满足某些条件的所有可能解的算法。

class Solution:
 def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
 # 对于给定的数组，排序使得相同数字相邻 candidates.sort()
 # 使用回溯法找到所有组合 self.res = []
 self.backtrack(candidates, target, [],0)
 return self.res def backtrack(self, candidates, remain, path, start):
 # 如果剩余的目标值为零，则添加当前路径到结果中 if remain ==0:
 self.res.append(path[:])
 return # 遍历候选数组，找到可以使用的数字 for i in range(start, len(candidates)):
 # 如果当前数字等于上一个数字，则跳过该数字，以避免重复组合 if i > start and candidates[i] == candidates[i-1]:
 continue # 如果当前数字大于剩余目标值，则跳过该数字 if candidates[i] > remain:
 break # 将当前数字添加到路径中，继续回溯 path.append(candidates[i])
 self.backtrack(candidates, remain-candidates[i], path, i+1)
 # 从路径中移除当前数字，继续回溯 path.pop()

# 测试用例1candidates = [10,1,2,7,6,1,5]
target =8solution = Solution()
print(solution.combinationSum2(candidates, target)) # 输出: [[1,1,6],[1,2,5],[1,7],[2,6]]

# 测试用例2candidates = [2,5,2,1]
target =5solution = Solution()
print(solution.combinationSum2(candidates, target)) # 输出: [[1,2,2],[5]]