39. 组合总和 - 力扣(LeetCode)
思路:
递归参数:数组candidates,目标和target,记录路径的path数组,for循环的起始index。
递归出口:当path的和大于target时,return;当path的和等于target时,找打满足条件的组合,收集结果,return。
单层递归逻辑:for循环从index开始遍历数组candidates:先将数字加入path中,再调用递归函数(因为同一个数字可以重复选取,所以index的值为i),最后弹出path数组的最后一个元素。
class Solution(object):def back(self,candidates,target,path,index):if sum(path)>target:returnif sum(path)==target:self.result.append(path[:])returnfor i in range(index,len(candidates)):path.append(candidates[i])self.back(candidates,target,path,i)path.pop()def combinationSum(self, candidates, target):self.result=[]self.back(candidates,target,[],0)return self.result