建立个大型网站需要多少投入,上海软件开发工程师工资一般多少,科技vi设计,找模板题目描述#xff1a;
给定一个候选人编号的集合 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意#xff1a;解集不能包含重复的组合。
代码思路#xff…题目描述
给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意解集不能包含重复的组合。
代码思路
排序 首先对 candidates 数组进行排序。排序的目的是为了后续能够方便地处理重复元素并且有助于提前终止搜索当当前数字已经大于剩余需要达到的目标值时。 初始化结果列表 创建一个空列表 ans用于存储所有满足条件的组合。 定义回溯函数 find(s, use, remain) 是一个递归函数用于寻找所有可能的组合。 s 是当前搜索的起始索引用于避免重复使用数组中的同一个元素。use 是当前已经选择的数字列表组合。remain 是当前还需要达到的目标值。 回溯逻辑 遍历从索引 s 到数组末尾的每个元素。如果当前元素与前一个元素相同i s and candidates[i-1] candidates[i]则跳过当前循环迭代以避免重复组合。如果当前元素等于剩余目标值 remain则将当前组合 use [c] 添加到结果列表 ans 中并返回结束当前递归路径。如果当前元素小于剩余目标值 remain则递归调用 find 函数更新起始索引为 i1因为当前元素已被使用更新已使用的数字列表为 use [c]更新剩余目标值为 remain - c。如果当前元素大于剩余目标值 remain则直接返回结束当前递归路径因为后续元素只会更大无法再达到目标值。 启动回溯 调用 find(0, [], target) 开始回溯过程初始时起始索引为 0已使用的数字列表为空剩余目标值为 target。 返回结果 最后返回结果列表 ans其中包含了所有满足条件的独特组合。
代码实现
class Solution:def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]:candidates.sort()ans []def find(s,use,remain):for i in range(s,len(candidates)):c candidates[i]if is and candidates[i-1]candidates[i]:continueif c remain:ans.append(use [c])return if c remain:find(i1,use [c], remain - c)if c remain:returnfind(0,[], target)return ans
