資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究Python中的組合求和
假設我們有一組候選數字（所有元素都是唯一的）和一個目標數字。我們必須找到候選者中所有唯一的組合，其中候選數字之和等於給定的目標。相同的重複數字可以從候選者中無限次選擇。因此，如果元素是[2,3,6,7]，目標值為7，則可能的輸出將是[[7], [2,2,3]]
讓我們看看步驟：
我們將以遞迴的方式解決這個問題。遞迴函式名為solve()。它接收一個數組來儲存結果，一個對映來儲存記錄，目標值和一個不同的元素列表。最初，res陣列和對映為空。solve方法的工作方式如下：
- 如果目標為0，則
- temp := 列表中存在的元素列表
- temp1 := temp，然後對temp排序
- 如果對映中不存在temp，則將temp插入對映並將其值設定為1，將temp插入res
- 返回
- 如果temp < 0，則返回
- 對於範圍從i到元素列表長度的x，
- 將elements[x]插入當前
- solve(elements, target – elements[x], res, map, i, current)
- 從當前列表中刪除索引為（current長度 – 1）的元素
讓我們看看下面的實現來更好地理解：
示例
class Solution(object):
def combinationSum(self, candidates, target):
result = []
unique={}
candidates = list(set(candidates))
self.solve(candidates,target,result,unique)
return result
def solve(self,candidates,target,result,unique,i = 0,current=[]):
if target == 0:
temp = [i for i in current]
temp1 = temp
temp.sort()
temp = tuple(temp)
if temp not in unique:
unique[temp] = 1
result.append(temp1)
return
if target <0:
return
for x in range(i,len(candidates)):
current.append(candidates[x])
self.solve(candidates,target-candidates[x],result,unique,i,current)
current.pop(len(current)-1)
ob1 = Solution()
print(ob1.combinationSum([2,3,6,7,8],10))輸入
[2,3,6,7,8] 10
輸出
[[2, 8], [2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 2, 6], [3, 7]]
更新於：2020年5月4日
2K+ 瀏覽量
廣告