leetcode-39-Combination Sum

Drummor 發布于2019-07-30 15:43 / 2745人閱讀

摘要：分為每次從里邊循環所有數，已有值減去所有數，新值作為已有值，繼續處理。遇到返回保存，負數去掉

"""
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)

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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