您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“Python組合總和怎么實(shí)現(xiàn)”,感興趣的朋友不妨來看看。本文介紹的方法操作簡(jiǎn)單快捷,實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“Python組合總和怎么實(shí)現(xiàn)”吧!
給定一個(gè)無重復(fù)元素的數(shù)組 candidates 和一個(gè)目標(biāo)數(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 中的每個(gè)元素都是獨(dú)一無二的。
1 <= target <= 500
先審題,題目給定無重復(fù)元素?cái)?shù)組和目標(biāo)值 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],因?yàn)檫@兩者就被視為與 [2,2,3] 為重復(fù)的組合,這里需要特別注意。
在這里 $\color{red}{?}$ 表示不選擇此元素,這樣就可以避免元素組合重復(fù)的情況,$\color{green}{?}$ 表示當(dāng)前路徑選擇元素和大于目標(biāo)值 target,而 $\color{green}{?}$ 則表示當(dāng)前路徑選擇元素和等于目標(biāo)值,可以將此組合添加到返回列表中。
在上面的圖例中,只是簡(jiǎn)單畫出了一個(gè)分支的情況,但是其他分支選擇的策略相同,這里就省略了。若有不太明白的地方,建議可以自行在草稿上進(jìn)行補(bǔ)全,也幫助自己理解。
那么就按照上面圖例中的思路,用代碼進(jìn)行實(shí)現(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: 組合中的元素和 """ # 基準(zhǔn)條件 # 當(dāng)元素和大于目標(biāo)值,直接返回 if total > target: return # 當(dāng)元素和等于目標(biāo)值,將組合添加到結(jié)果中,返回 if total == target: ans.append(tmp[::]) return # 進(jìn)入分支,同時(shí)避免重復(fù)組合 for i in range(idx, len(candidates)): # 更新 total 值, total += candidates[i] # 同時(shí)將當(dāng)前元素嘗試添加到組合中 tmp.append(candidates[i]) # 再次進(jìn)入遞歸 # 這里可以看文章圖例,遞歸向下,可選元素是從自身開始選擇 # 這里同時(shí)也能避免組合重復(fù),因?yàn)椴粫?huì)再次選擇索引 i 前面對(duì)應(yīng)的元素 helper(i, total) # 回溯,回退組合元素及 total 值 tmp.pop() total -= candidates[i] total = 0 helper(0, total) return ans
到此,相信大家對(duì)“Python組合總和怎么實(shí)現(xiàn)”有了更深的了解,不妨來實(shí)際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。