leetcode-39-Combination Sum

Drummor 发布于2019-07-30 15:43 / 2531人阅读

摘要：分为每次从里边循环所有数，已有值减去所有数，新值作为已有值，继续处理。遇到返回保存，负数去掉

"""
39. Combination Sum
Description
HintsSubmissionsDiscussSolution
Given a set of candidate numbers (C) (without duplicates) and a target number (T),
find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]

"""
import copy


class Solution:
    def recursive(self,candidates,target_cur,nums_in,numlist_cur):
        """
        分为  每次从set里边循环所有数，已有值减去所有数，新值作为已有值，继续处理。遇到0 返回保存，负数去掉
        :param candidates:
        :param target:
        :return:
        """
        # numlist_cur_in=numlist_cur
        outlist=[]
        for index,num in enumerate(candidates):
            target_cur_new=target_cur-num
            if target_cur_new==0:
                numlist_cur.append(nums_in+[num])
            elif target_cur_new>0:
                self.recursive(candidates[index:],target_cur_new,nums_in+[num],numlist_cur)
            else:
                pass



    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        numlist_cur=[]

        out=self.recursive(candidates,target,[],numlist_cur)
        return numlist_cur
        # print(out)
        # print(numlist_cur)
class Solution_:
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        self.rec(candidates, target, [], res)
        return res


    def rec(self, candidates, target, path, res):
        if target < 0:
            return
        if target == 0:
            res.append(path)
            return
        for i in range(len(candidates)):
            self.rec(candidates[i:], target - candidates[i], path + [candidates[i]], res)
if __name__=="__main__":
    st=Solution()
    nums=[2, 3, 6, 7]
    target=6
    out=st.combinationSum(nums,target)
    print(out)

服务器托管私有云 sum hibernate 分页 sum three-sum two-sum

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/41423.html

leetcode40 combination sum 2

摘要：参考思路和非常类似，只是这里需要增加进行重复处理的部分。题目要求题目中新添的要求包括数组中存在重复值，而且数组中每个值只可以使用一次。需要注意的是，既然数组中存在重复的值，就要注意可能会将重复的情况加入结果数组。参考思路和leetcode39 combination sum 非常类似，只是这里需要增加进行重复处理的部分。请参考我对leetcode39进行解答的这篇博客。题目要求 ...

Code4App 2019-08-16 10:33 评论0 收藏0
leetcode39 combination sum

摘要：在这道题中，我结合了递归的思想来。就是将当前的值作为一个潜在的结果值加入一个结果数组将数组作为当前结果传入下一轮递归。题目要求 Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the ca...

luoyibu 2019-08-16 10:33 评论0 收藏0
[Leetcode-Tree] Path Sum I II III

摘要：解题思路利用递归，对于每个根节点，只要左子树和右子树中有一个满足，就返回每次访问一个节点，就将该节点的作为新的进行下一层的判断。代码解题思路本题的不同点是可以不从开始，不到结束。代码当前节点开始当前节点左节点开始当前节点右节点开始 Path SumGiven a binary tree and a sum, determine if the tree has a root-to-lea...

notebin 2019-08-16 10:26 评论0 收藏0
[Leetcode] Path Sum I & II & III 路径和1,2,3

摘要：只要我们能够有一个以某一中间路径和为的哈希表，就可以随时判断某一节点能否和之前路径相加成为目标值。最新更新请见：https://yanjia.me/zh/2019/01/... Path Sum I Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that addin...

caiyongji 2019-08-14 12:25 评论0 收藏0
动态规划法（八）最大子数组问题（maximum subarray problem）

摘要：动态规划法用表示最大子数组的结束下标为的情形，则对于，有这样就有了一个子结构，对于初始情形，遍历就能得到这个数组，其最大者即可最大子数组的和。动态规划法想法巧妙，运行效率也高，但是没有普遍的适用性。问题简介本文将介绍计算机算法中的经典问题——最大子数组问题（maximum subarray problem）。所谓的最大子数组问题，指的是：给定一个数组A，寻找A的和最大的非空连续...

jzman 2019-07-30 16:46 评论0 收藏0