超過LeetCode40時間限制

我正在研究 LeetCode 40。組合總和 II

給定一組候選編號（candidates）和一個目標編號（target），找出候選編號總和為 target 的所有唯一組合。

候選中的每個數字在組合中只能使用一次。

注意：解決方案集不得包含重復的組合。

我下面的代碼一直有效，直到候選人集合變得太大，然后我得到“超出時間限制”。我認為所有的遞回都創建了太多的回圈。我顯然可以復制教程來獲得答案，但我試圖弄清楚如何更新我的代碼以作業，以便更好地理解遞回是如何作業的。

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        answers = []
        strings = []
        total = sum(candidates)
        if total < target:
            return []
        def backtrack(total, array, index):
            if total == 0:
                string = ''
                for each in array:
                    string  = str(each)
                if string not in strings:
                    answers.append(array)
                    strings.append(string)
                    return
            if index >= len(candidates):
                return
            for each in range(index, len(candidates)):
                backtrack(total - candidates[each], array   [candidates[each]], each   1)
                backtrack(total, array, each   1)
        backtrack(target, [], 0)
        return answers

uj5u.com熱心網友回復：

對候選項進行排序是個好主意，但您不要使用它。僅當 total-candidate[i]>0 時才應撤回，如果 <0 則中斷，如果 =0 則回傳

uj5u.com熱心網友回復：

一些影響性能的問題：

• 當total變為負數時，繼續遞回程序是沒有用的：它只會變得更負數。

• 第二個呼叫是實作與回圈backtrack相同的想法。for考慮在回圈中所有可能的值 foreach 1將被傳遞給backtrack(total, array, each 1). 但還要注意，在遞回樹中更深一層，所有這些——除了第一個——都被重新制作了！所以要么洗掉，要么backtrack(total, array, each 1)保留它，然后洗掉for回圈。

• 當兩個連續的值相同，并且已經對這兩個中的第一個進行了遞回呼叫時，使用重復值進行遞回呼叫是沒有用的。在那一刻，可供選擇的值少了一個，而且總數是一樣的，所以不能從中產生任何新的組合。因此，如果我們進行for回圈（見前一點），那么只對不同的值進行遞回呼叫（它們第一次出現）。

• 用于查找重復結果的字串連接適用于測驗用例，但它有點棘手，因為數字被連接在一起。例如，當1, 2, 3被字串化時，它變為“123”。但是 1, 23 也會像這樣被字串化，這可能會導致假陰性。所以這實際上是 LeetCode 上未被檢測到的代碼中的錯誤。您可以通過使用分隔符來解決此問題。

這是考慮到這些要點的代碼：

class Solution: 
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        answers = []
        strings = []
        total = sum(candidates)
        if total < target:
            return []
        def backtrack(total, array, index):
            if total == 0:
                string = ''
                for each in array:
                    string  = "_"   str(each)  # Separate the values
                if string not in strings:
                    answers.append(array)
                    strings.append(string)
                    return
            if index >= len(candidates) or total < 0:  # give up when total becomes negative
                return
            current = -1
            for each in range(index, len(candidates)):
                if candidates[each] != current: # Avoid duplicates
                    current = candidates[each]
                    backtrack(total - current, array   [current], each   1)
                # Don't make another recursive call here. The for-loop is already skipping candidates
        backtrack(target, [], 0)
        return answers

仍有改進的余地。你可以想到以下幾點：

• Your code currently checks that the total is not greater than the overall sum. You could extend this, and verify that the total is not greater than the remaining sum, during the recursive process. You would prepare a list with all these "remaining" sums before starting the recursion, and then check the total against the relevant value in that list.

• if string not in strings is not so efficient when strings is a list. It would be better to use a set for strings.

• Instead of using strings as identifiers, you could create tuples instead of sub lists. These are hashable, so if you store them in an overall set instead of list, you will not get duplicates. Then at the very end you can convert that set of tuples to the final list of lists.

標籤：

上一篇：我怎樣才能得到一個可用的組合來代替重復？

下一篇：獲取深度嵌套物件中鍵的值