39.组合总和

正好刚做完求数独复习完回溯，这个直接就做了。注意candidates[index:]这里，从index开始搜索可以保证 没有重复的，减少搜索空间

class Solution:
    def select(self, a, candidates, target) -> List[List[int]]:
        """
        :param a: 已经选择的元素
        :param target: 目标结果
        """
        if sum(a) == target:
            return [a]
        if sum(a) > target:
            return []
        result = []
        for index, candidate in enumerate(candidates):
            res = self.select(a + [candidate], candidates[index:], target)
            if res:
                result.extend(res)
        return result

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        return self.select([], candidates, target)

评论