国外哪些网站可以注册域名,百度推广代运营,桂林城乡建设局网站,怎么做会员自动售卡网站给定一个候选人编号的集合 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意#xff1a;解集不能包含重复的组合。 示例 1: 输入: candidates [10,1,2,7,6,1… 给定一个候选人编号的集合 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 Listclass 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[:])returnfor 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])# 递归寻找剩余目标值的组合注意是i1因为每个数字只能用一次backtrack(i 1, target - candidates[i], current)# 回溯移除当前数字current.pop()# 先排序便于处理重复元素candidates.sort()result []backtrack(0, target, [])return resultif __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 # 返回 Falseside_length total_length // 4 # 计算每个边的目标长度matchsticks.sort(reverseTrue) # 从大到小排序优化回溯过程sides [0] * 4 # 初始化四个边的当前长度为0def 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 # 如果成功返回 Truesides[i] - matchsticks[index] # 回溯撤销选择return False # 如果无法拼成正方形返回 Falsereturn 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不能拼成正方形
