本篇內(nèi)容主要講解“Python組合總和怎么實現(xiàn)”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學(xué)習“Python組合總和怎么實現(xiàn)”吧!

我們提供的服務(wù)有：成都網(wǎng)站設(shè)計、成都網(wǎng)站建設(shè)、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認證、橫峰ssl等。為千余家企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的橫峰網(wǎng)站制作公司

題目

---

給定一個無重復(fù)元素的數(shù)組 candidates 和一個目標數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。

candidates 中的數(shù)字可以無限制重復(fù)被選取。

說明：

• 所有數(shù)字（包括 target）都是正整數(shù)。

• 解集不能包含重復(fù)的組合。

示例 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]
]

提示：

• 1 <= candidates.length <= 30

• 1 <= candidates[i] <= 200

• candidate 中的每個元素都是獨一無二的。

• 1 <= target <= 500

解題思路

---

思路：回溯

先審題，題目給定無重復(fù)元素數(shù)組和目標值 target，要求找出數(shù)組中所有可以使數(shù)組元素和為 target 的組合。

其中數(shù)組中的元素都為正整數(shù)，可以重復(fù)使用數(shù)組中的元素，但是解集中不能存在重復(fù)的組合。

這里可以看示例 1：

輸入：candidates = [2,3,6,7], target = 7,
所求解集為：
[
  [7],
  [2,2,3]
]

這里答案并沒有 [2,3,2] 或 [3,2,2]，因為這兩者就被視為與 [2,2,3] 為重復(fù)的組合，這里需要特別注意。

在這里 $\color{red}{?}$ 表示不選擇此元素，這樣就可以避免元素組合重復(fù)的情況，$\color{green}{?}$ 表示當前路徑選擇元素和大于目標值 target，而 $\color{green}{?}$ 則表示當前路徑選擇元素和等于目標值，可以將此組合添加到返回列表中。

在上面的圖例中，只是簡單畫出了一個分支的情況，但是其他分支選擇的策略相同，這里就省略了。若有不太明白的地方，建議可以自行在草稿上進行補全，也幫助自己理解。

那么就按照上面圖例中的思路，用代碼進行實現(xiàn)，具體如下。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # 結(jié)果列表
        ans = []
        # 可能的組合
        tmp = []

        def helper(idx, total):
            """回溯，求組合總和
            Args:
                idx: 選取元素索引
                total: 組合中的元素和
            """
            # 基準條件
            # 當元素和大于目標值，直接返回
            if total > target:
                return
            # 當元素和等于目標值，將組合添加到結(jié)果中，返回
            if total == target:
                ans.append(tmp[::])
                return
            
            # 進入分支，同時避免重復(fù)組合
            for i in range(idx, len(candidates)):
                # 更新 total 值，
                total += candidates[i]
                # 同時將當前元素嘗試添加到組合中
                tmp.append(candidates[i])
                # 再次進入遞歸
                # 這里可以看文章圖例，遞歸向下，可選元素是從自身開始選擇
                # 這里同時也能避免組合重復(fù)，因為不會再次選擇索引 i 前面對應(yīng)的元素
                helper(i, total)
                # 回溯，回退組合元素及 total 值
                tmp.pop()
                total -= candidates[i]
            
        total = 0
        helper(0, total)
        return ans

到此，相信大家對“Python組合總和怎么實現(xiàn)”有了更深的了解，不妨來實際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學(xué)習！

分享文章：Python組合總和怎么實現(xiàn)
文章網(wǎng)址：http://chinadenli.net/article48/gdjjhp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站制作、App開發(fā)、做網(wǎng)站、、營銷型網(wǎng)站建設(shè)、搜索引擎優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)