递归（3）----力扣40组合数2，力扣473火柴拼正方形
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
示例 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,2], target = 5, 输出: [ [1,2,2], [5] ]
from typing import List
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
def backtrack(start: int, target: int, current: List[int]):
if target == 0:
result.append(current[:])
return
for i in range(start, len(candidates)):
# 剪枝：如果当前数字大于目标值，后面的数字更大，直接跳出
if candidates[i] > target:
break
# 跳过重复数字，确保不会生成重复组合
if i > start and candidates[i] == candidates[i-1]:
continue
# 选择当前数字
current.append(candidates[i])
# 递归寻找剩余目标值的组合，注意是i+1因为每个数字只能用一次
backtrack(i + 1, target - candidates[i], current)
# 回溯，移除当前数字
current.pop()
# 先排序，便于处理重复元素
candidates.sort()
result = []
backtrack(0, target, [])
return result
if __name__ == '__main__':
s = Solution()
print(s.combinationSum2([10,1,2,7,6,1,5], 8))
print(s.combinationSum2([2,5,2,1,2], 5))
例子 假设我们有一个候选数字列表 candidates = [1, 2, 3]，我们想要找到所有组合，使得它们的和等于 target = 4。 递归过程 初始调用： backtrack(0, 4, [])：从索引 0 开始，目标值为 4，当前组合为空。 2. 第一层递归： 选择 candidates[0] = 1： current = [1]，目标变为 4 - 1 = 3，调用 backtrack(1, 3, [1])。 选择 candidates[1] = 2： current = [2]，目标变为 4 - 2 = 2，调用 backtrack(2, 2, [2])。 选择 candidates[2] = 3： current = [3]，目标变为 4 - 3 = 1，调用 backtrack(3, 1, [3])。 3. 第二层递归： 对于 current = [1]，目标为 3： 选择 candidates[1] = 2： current = [1, 2]，目标变为 3 - 2 = 1，调用 backtrack(2, 1, [1, 2])。 选择 candidates[2] = 3： current = [1, 3]，目标变为 3 - 3 = 0，找到一个有效组合 [1, 3]，返回。 4. 继续探索： 对于 current = [2]，目标为 2： 选择 candidates[2] = 3，目标变为 2 - 3 = -1，无效，返回。 对于 current = [1, 2]，目标为 1： 选择 candidates[2] = 3，目标变为 1 - 3 = -2，无效，返回。 5. 最终结果： 通过递归的方式，我们会找到所有有效的组合，最终结果为 [[1, 3], [2, 2]]。 总结 这个例子展示了如何通过递归探索所有可能的组合，直到找到所有和为目标值的组合。每次选择一个数字并递归调用，直到满足条件或超出目标值。
你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
如果你能使这个正方形，则返回 true ，否则返回 false 。
示例 1:
输入: matchsticks = [1,1,2,2,2] 输出: true 解释: 能拼成一个边长为2的正方形，每边两根火柴。
示例 2:
输入: matchsticks = [3,3,3,3,4] 输出: false 解释: 不能用所有火柴拼成一个正方形。
from typing import List # 导入 List 类型
class Solution:
def makesquare(self, matchsticks: List[int]) -> bool:
total_length = sum(matchsticks) # 计算所有火柴棒的总长度
# 如果总长度不能被4整除，无法形成正方形
if total_length % 4 != 0:
return False # 返回 False
side_length = total_length // 4 # 计算每个边的目标长度
matchsticks.sort(reverse=True) # 从大到小排序，优化回溯过程
sides = [0] * 4 # 初始化四个边的当前长度为0
def backtrack(index: int) -> bool:
if index == len(matchsticks): # 如果所有火柴棒都已使用
# 检查四个边是否相等
return all(side == side_length for side in sides) # 返回是否每个边都等于目标边长
for i in range(4): # 遍历四个边
if sides[i] + matchsticks[index] <= side_length: # 如果当前边加上火柴棒不超过目标边长
sides[i] += matchsticks[index] # 选择当前火柴棒，加入到当前边
if backtrack(index + 1): # 递归处理下一个火柴棒
return True # 如果成功，返回 True
sides[i] -= matchsticks[index] # 回溯，撤销选择
return False # 如果无法拼成正方形，返回 False
return backtrack(0) # 从第一个火柴棒开始回溯
if __name__ == '__main__':
s = Solution() # 创建 Solution 类的实例
print(s.makesquare([1, 1, 2, 2, 2])) # 输出: True，能拼成正方形
print(s.makesquare([3, 3, 3, 3, 4])) # 输出: False，不能拼成正方形