Leetcode_39【组合总和】

时间：2019-12-20 10:42:54 收藏：0 阅读：76

文章目录：

题目
脚本一
脚本一逻辑
脚本二
脚本二逻辑
shell处理分享

题目：

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

脚本一：【用时：630ms】

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        list1 = []
        list3 = []
        ret = []
        for i in candidates:
            list1.append(list(range(i,i+1)))
            list2 = list1[:]
        def diedai(l1,l2,target):
            n1 = len(l1)
            for i in range(n1):
                for j in l2:
                    bb = l1[i] + j
                    if sum(bb) <= target:
                        bb.sort()
                        l1.append(bb)
        while list2:
            list3 = []
            for i in list2:
                if sum(i) == target:
                    if i not in ret:
                        ret.append(i)
                    list3.append(i)
                elif sum(i) < target:
                    list3.append(i)
            list2 = list3
            if list2:
                n2 = len(list2)
                diedai(list2,list1,target)
                del list2[0:n2]
            else:
                break
        return(ret)

脚本一逻辑：

此题使用的是树形分支法求解：主要的处理逻辑如下：
- 以[2,3,6,7]，target = 7为例；此处只选择列表中一个元素"2"进行讲解：2可以分支为[2,2],[2,3],[2,6],[2,7];遍历这些生成的元素，对那些列表总和大于target的剔除掉，对那些列表总和等于target记录到特定列表中，小于target的进行下一次循环；在进入下一次循环前，把原列表内容剔除，也就是剔除"2"
- 下次遍历对象为[2,2],[2,3],可分别生成[2,2,2],[2,2,3],[2,2,6],[2,2,7]和[2,3,2],[2,3,3],[2,3,6],[2,3,7],然后再进行上一次操作即可

脚本二：【用时：100ms】【转载】

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        def searchSum(candidates,target):
            res=[]
            for i in range(len(candidates)):
                num=candidates[i]
                if num<target:
                    #为了去重，从当前位置开始搜索解
                    l=searchSum(candidates[i:],target-num)
                    if l!=[]:
                        for ele in l:
                            ele.append(num)
                    res=res+l
                elif num==target:
                    res=res+[[num]]
            return res

        return searchSum(candidates,target)

脚本二逻辑：

此脚本是函数内嵌递归进行求解，相当有难度
在某些情况下，l就是res，但l是切片后的组合，需要加上切片前，target减去的num值
通过遍历给定列表的每个元素进行求解

shell处理分享：

https://blog.csdn.net/weixin_43428906/article/details/102923126

原文：https://www.cnblogs.com/mailong/p/12070897.html