题目链接
https://leetcode-cn.com/problems/combination-sum/
参考链接
方法1 回溯 剪枝
image.png
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
o=[]
st=[]
cnt=0
def huisu(dangqianzhuangtai,sousuokongjian):
if sum(dangqianzhuangtai)==target:
o.append(dangqianzhuangtai)
return 1
elif sum(dangqianzhuangtai)>target:
return 0
else:
for s in sousuokongjian:
t=dangqianzhuangtai[:]
if t!=[]:
if s<t[-1]:
continue
t.append(s)
a=huisu(t,sousuokongjian)
huisu([],candidates)
return o
