python实现leetcode之39. 组合总和

解题思路

递归
对于每一个数作递归操作
如果这个数item小于目标值target，包括这个数在内的数组合出target-item，在每个组合前面附加上item就是所有方案
如果这个数等于target，这就是方案，包含一个数
否则无解

39. 组合总和

代码

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        rtv = []
        for idx, item in enumerate(candidates):
            if item < target:
                others = candidates[idx:]
                more = self.combinationSum(others, target-item)
                for x in more:
                    rtv.append([item, *x])
            elif item == target:
                rtv.append([item])
        return rtv

效果图