当前位置: 首页 > 后端技术 > Python

组合和(Python3)

时间:2023-03-26 11:13:37 Python

题目描述:给定一个没有重复元素的数组candidates和一个目标数target,找出candidates中所有可以使数字之和为target的组合。候选人中的数字可以无限次重复选择。解释:所有数字(包括目标)都是正整数。解决方案集不能包含重复的组合。例1:输入:candidates=[2,3,6,7],target=7,解集为:[[7],[2,2,3]]解题思路:我用的是笨办法,找出满足目标的数组的全排列,在插入到解集之前判断解集中是否存在该排列,如果存在则不插入。全排列的解法查看全排列(Python3)代码如下( ̄▽ ̄):classSolution:defcombinationSum(self,candidates:List[int],target:int)->List[List[int]]:self.re=[]self.target=targetself.candidates=candidatesself.sub_combinationSum(target,[])returnself.redefsub_combinationSum(self,target,temp):iftarget<0:returniftarget==0:温度。sort()iftempnotinself.re:self.re.append(temp)else:foriinself.candidates:self.sub_combinationSum(target-i,temp+[i])时空复杂度:来源:ForceBuckle(LeetCode)链接:https://leetcode-cn.com/probl...