LeetCode讲解篇之39. 组合总和

发布时间:2024年01月13日

题目描述

在这里插入图片描述

题解思路

首先排序数组,然后开始选择数字,当选择数字num后,在去选择大于等于num的合法数字,计算过程中的数字和,直到选数字和等于target, 加入结果集,若数字和大于target则直接退出当前搜索,因为数字是从小到大排序的,如果当前数字和都大于target了,那么之后的选择过程数字和只会更大,所以之后的搜索为无效搜索,直接剪枝

题解代码

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        n = len(candidates)
        candidates.sort()
        res = []
        tmp = []
        sum = 0
        start = 0
        def dfs():
            nonlocal sum
            nonlocal start
            for i in range(start, n):
                num = candidates[i]
                if sum + num == target:
                    tmp.append(num)
                    res.append([num for num in tmp])
                    tmp.pop()
                    return
                if sum + num > target:
                    return
                sum += num
                tmp.append(num)
                start = i
                dfs()
                tmp.pop()
                sum -= num

        dfs()                
        return res
文章来源:https://blog.csdn.net/qq_67733273/article/details/135570391
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。