leetcode 39 组合总和

通过回溯,以及按大小剪枝,因为组合问题所以需要固定一个顺序遍历,因为不同顺序也被视为一个组合。保证path数组中的顺序是升序的。

遇到这一类相同元素不计算顺序的问题,我们在搜索的时候就需要按某种顺序搜索。
注意:这里的顺序不仅仅指数组 candidates 有序,还指按照一定顺序搜索结果。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(path,result,target):
            if target==0:
                result.append(path[:])
                return
            if target<0: 
                return 
            for j in range(len(candidates)):
                if len(path)!=0 and path[-1]>candidates[j]:continue
                path.append(candidates[j])
                dfs(path,result,target-candidates[j])
                path.pop()
        result=[]
        dfs([],result,target)
        return result

Python3 的 [1, 2] + [3] 语法生成了新的列表,一层一层传到根结点以后,直接 res.append(path) 就可以了;
基本类型变量在传参的时候,是复制,因此变量值的变化在参数里体现就行,所以 Python3 的代码看起来没有「回溯」这个步骤。

有些朋友可能会疑惑什么时候使用 used 数组,什么时候使用 begin 变量。这里为大家简单总结一下:

排列问题,讲究顺序(即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时),需要记录哪些数字已经使用过,此时用 used 数组;
组合问题,不讲究顺序(即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时),需要按照某种顺序搜索,此时使用 begin 变量。

作者:liweiwei1419
链接:https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

每次从当前搜索的起点出发,注意因为可以重复从当前节点出发,如果不能重复那么从当前加1的位置出发。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(i,path,result,target):
            if target==0:
                result.append(path[:])
                return
            #if target<0: 
                #return 
            for j in range(i,len(candidates)):

                if target-candidates[j]<0:continue
                path.append(candidates[j])
                dfs(j,path,result,target-candidates[j])
                path.pop()
        if len(candidates)==0:
            return []
        result=[]
        dfs(0,[],result,target)
        return result
全部评论

相关推荐

点赞 评论 收藏
分享
牛客5655:其他公司的面试(事)吗
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
11-21 17:16
科大讯飞 算法工程师 28.0k*14.0, 百分之三十是绩效,惯例只发0.9
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务