程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode Combination Sum II

LeetCode Combination Sum II

編輯:C++入門知識

LeetCode Combination Sum II


LeetCode解題之Combination Sum II


原題

在一個數組(存在重復值)中尋找和為特定值的組合。

注意點:

所有數字都是正數 組合中的數字要按照從小到大的順序 原數組中的數字只可以出現一次 結果集中不能夠有重復的組合

例子:

輸入: candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
輸出: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

解題思路

這道題和 Combination Sum 極其相似,主要的區別是Combination Sum中的元素是沒有重復的,且每個元素可以使用無限次;而這題中的元素是有重復的,每個元素最多只能使用一次。最開始的想法是加下一個元素時不要考慮當前元素,且把結果用集合存儲以防止重復的組合出現,但結果超時了。改用手動把所有與當前元素相等的元素都去掉即可。

AC源碼

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if not candidates:
            return []
        candidates.sort()
        result = []
        self.combination(candidates, target, [], result)
        return result

    def combination(self, candidates, target, current, result):
        s = sum(current) if current else 0
        if s > target:
            return
        elif s == target:
            result.append(current)
            return
        else:
            i = 0
            while i < len(candidates):
                self.combination(candidates[i + 1:], target, current + [candidates[i]], result)
                # ignore repeating elements
                while i + 1 < len(candidates) and candidates[i] == candidates[i + 1]:
                    i += 1
                i += 1


if __name__ == "__main__":
    assert Solution().combinationSum2([10, 1, 2, 7, 6, 1, 5], 8) == [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

歡迎查看我的Github來獲得相關源碼。


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved